글 읽기 - 14502 파이썬 코드 효율성 봐주세요.. 부탁드려요! 절실합니다

thdruddyd21 3년 전 0

브루트 포스 여서 combinations로 모든 index 구해서 그냥 bfs 하는건데... pypy3로는 간신히 통과고 python3는 60%에서 시간초과 떠버리네요 .. 어느 부분을 어떻게 고치면 좋을지 코드 첨삭 부탁드려요 감사합니다 !

from _collections import deque
from itertools import combinations
import sys
import copy

opx = [1,-1,0,0]
opy = [0,0,1,-1]
safe = []
zone = []
wall = 0
N, M = map(int, sys.stdin.readline().split())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, list(sys.stdin.readline().split()))))
temp = copy.deepcopy(matrix)

for i in range(N):
    for j in range(M):
        if matrix[i][j] == 0:
            zone.append([i,j])
        elif matrix[i][j] == 1:
            wall += 1
def spread_virus(i,j):

    visit = {}
    queue = deque()
    queue.append([i,j])
    visit[str(i)+str(j)] = True

    while queue:
        ax, ay = queue.popleft()
        for k in range(4):
            xx = ax + opx[k]
            yy = ay + opy[k]

            if 0<=xx<=N-1 and 0<=yy<=M-1:
                if matrix[xx][yy] == 0 and str(xx)+str(yy) not in visit:
                    queue.append([xx,yy])
                    matrix[xx][yy] = 2
                    visit[str(i) + str(j)] = True

permute = combinations(zone,3)
m = 0
for k in permute:
    a, b, c = k[0], k[1], k[2] #index of wall
    matrix[a[0]][a[1]] = 1
    matrix[b[0]][b[1]] = 1
    matrix[c[0]][c[1]] = 1

    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 2:
                spread_virus(i, j)
    count = 0
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 0:
                count += 1

    if m < count:
        m = count
    matrix = copy.deepcopy(temp)
print(m)

shg9411 3년 전 1

deepcopy는 굉장히 느립니다.

복사를 하지 않는 방법으로 하시면 통과하실 수 있습니다.

zxcv5052 3년 전 0

@shg9411 혹시 deepcopy 말고는 어떤식으로 해야되나요? 파라미터로 하면 되나요?ㅠㅠ

java로 작성했는데 시간이 쫌 많이나와서요 ㅠ

shg9411 3년 전 2

벽을 세우는 것에 대해서 dfs를 사용하시고 3개가 되었을 때 bfs를 하시면 됩니다.

def dfs(위치,개수):
    if 개수==3:
        res = max(bfs(),res)
        return
    나머지 = 벽 세우기
    

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

14502 파이썬 코드 효율성 봐주세요.. 부탁드려요! 절실합니다

thdruddyd21 3년 전 0

shg9411 3년 전 1

zxcv5052 3년 전 0

shg9411 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말