[Python] 백준, 7576(BFS)

https://www.acmicpc.net/problem/7576

7576번: 토마토

무려 7번이나 시간 초과가 발생해서 머리가 터질뻔했다. 답은 의외로 단순한 곳에 있긴 했는데, queue 사용 시, deque모듈을 쓰지 않은 것이 원인이었다. 

 

이 문제가 BFS인 이유는 총 걸린 시간을 구해야 한다는 점과 익은 토마토가 여러군데에 심어져 있다는 점으로 보았을 때, 같은 레벨에 위치한 노드들부터 살피면서 나아가는 탐색이기 때문이다. 

 

처음 추구한 방향은 한 큐가 끝날 때 day값을 +1 해주는 풀이였는데, 이게 생각보다 쉽지가 않아서 결국 익숙한 방식인 tree의 요소에 값을 더해나가면서 가장 큰 값을 갱신해주는 방식을 택하게 되었다.

 

 

# PYTHON CODE (1)

from collections import deque
import sys

m, n = map(int, sys.stdin.readline().split())

tree = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
queue = deque()
day = -2

for i in range(m):
    for j in range(n):
        if tree[j][i] == 1:
            queue.append([j, i])

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while queue:
    y, x = queue.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and tree[ny][nx] == 0:
            queue.append([ny, nx])
            tree[ny][nx] = tree[y][x] + 1

flag = False

for i in tree:
    for j in i:
        if j == 0:
            flag = True
            break
        day = max(day, j)
    if flag:
        print(-1)
        break

if not flag:
    if day == -1:
        print(0)
    else:
        print(day - 1)

시간 초과의 원인에 대해서 위에 언급한 것과 같이, 리스트 대신 전부 deque모듈로 처리를 해주었다.

 

 

# PYTHON CODE (2)

import sys

m, n = map(int, sys.stdin.readline().split())

tree = []
queue = []
next_queue = []
day = 0
is_full = False

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    for j, k in enumerate(temp):
        if k == 1:
            queue.append([i, j])
    tree.append(temp)

if len(queue) == m * n:
    is_full = True

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while queue:

    for y, x in queue:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and tree[ny][nx] == 0:
                next_queue.append([ny, nx])
                tree[ny][nx] = 1

    queue = next_queue
    next_queue = []
    day += 1

flag = False

for i in tree:
    for j in i:
        if j == 0:
            flag = True
            break
    if flag:
        print(-1)
        break

if not flag:
    if is_full:
        print(0)
    else:
        print(day - 1)

다른 사람들의 풀이를 보면서, 처음 내가 생각했던 풀이는 단순히 배열이 두개가 있으면 된다는 것을 직감했고 바로 응용해서 다른 풀이를 작성하였다.

 

우수한 풀이 중에서 중복되는 코드인 초반  tree에 input값을 할당하는 반복문과 값이 1인 요소를 찾는 반복문을 하나로 결합하여 작성한 풀이가 있어 참고했는데, 이 관찰력이 참 소름 돋는 것 같다.

 

is_full은 배열이 전부 1인 경우를 고려한 값인데, 다른 풀이들에서는 발견되지 않는 걸로 보아 이걸 고려하지 않아도 알아서 처리되는가하는 의문이 든다.