파이썬. 시간초과의 늪

#7576 토마토 https://www.acmicpc.net/problem/7576

7576번: 토마토

M, N = map(int, input().split())

mat = []
visited = []
queue = []
for i in range(N):
    m = []
    b = []
    l = input().split()
    for x in range(M):
        tmp = int(l[x])
        m.append(tmp)
        if tmp == -1:
            b.append(True)
        elif tmp == 1:
            queue.append([i, x])
            b.append(True)
        else:
            b.append(False)
    mat.append(m)
    visited.append(b)

dr = [1, -1, 0, 0]
# B, U, R, L
dc = [0, 0, 1, -1]

cnt = 0
while queue:
    tmp = []
    for r, c in queue:
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if not visited[nr][nc]:
                    visited[nr][nc] = True
                    if mat[nr][nc] == 0:
                        mat[nr][nc] = 1
                        tmp.append([nr, nc])
    queue = tmp

    if len(queue) > 0:
        cnt += 1

if sum(sum(visited, [])) == N*M:
    print(cnt)
else:
    print(-1)

처음 제출했던 코드이다. 시간초과가ㅏ 나서 pypy3로 제출해서 정답에 성공했다.

 

그래도 설마설마하는 마음에

마지막 정답 출력부분의 이중 sum을 수정했다. (구글링)

 

M, N = map(int, input().split())

mat = []
visited = []
queue = []
for i in range(N):
    m = []
    b = []
    l = input().split()
    for x in range(M):
        tmp = int(l[x])
        m.append(tmp)
        if tmp == -1:
            b.append(True)
        elif tmp == 1:
            queue.append([i, x])
            b.append(True)
        else:
            b.append(False)
    mat.append(m)
    visited.append(b)

dr = [1, -1, 0, 0]
# B, U, R, L
dc = [0, 0, 1, -1]

cnt = 0
while queue:
    tmp = []
    for r, c in queue:
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < M:
                if not visited[nr][nc]:
                    visited[nr][nc] = True
                    if mat[nr][nc] == 0:
                        mat[nr][nc] = 1
                        tmp.append([nr, nc])
    queue = tmp

    if len(queue) > 0:
        cnt += 1

for i in mat:
    for j in i:
        if j == 0:
            print(-1)
            exit()

print(cnt)

기존의 정답출력방식은 방문노드를 논리값으로 표현한걸 전부 더해서 모든 노드 수와 같은지 확인했다. (모든 노드를 방문했는지 확인, -1 노드는 미리 True로 설정)

 

sum(2D-list, [])를 하게되면 2차원 리스트를 1차원으로 펴준다.

그 뒤  sum을 통해 합을 구했는데

 

하기야 list sum 자체가 선형적인 연산일 것 같다. O(n)

 

그래서 구글링을 통해 되게 단순하고 무식한 방법으로 변경했는데

 

저게 더 빠를줄이야...

 

깨달음의 하루