[코테] Bfs 토마토

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

시간초과 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(x, y, visited):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            if graph[nx][ny] == 0: 
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
            elif graph[nx][ny] != -1 and graph[nx][ny] != 1:
                if visited[nx][ny] == 0:
                    graph[nx][ny] = min(graph[nx][ny], graph[x][y] + 1)
                    queue.append((nx, ny))
                    visited[nx][ny] = 1


M, N = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(N):
    graph[i].extend(list(map(int, input().split())))

queue = deque()
for x in range(N):
    for y in range(M):
        if graph[x][y] == 1:
            visited = [[0 for _ in range(M)] for _ in range(N)]
            visited[x][y] = 1
            queue.append((x, y))
            bfs(x, y, visited)

answer = int(-1e9)
isValid = True
for x in range(N):
    for y in range(M):
        if graph[x][y] == 0:
            isValid = False
            break
        answer = max(answer, graph[x][y])
    if not isValid:
        break

answer = answer - 1 if isValid else -1
print(answer)

문제점

1. 문제에 주어진 모든 테스트케이스는 맞았지만, 시간 초과가 났다.

2. 로직

   1. 2차원 배열을 돌면서 1이 있는 경우 bfs를 수행한다.

   2. bfs로 가능한 모든 경우를 다 순회해서 그래프에 걸린 시간을 기록한다. (visited를 메인에서 호출할 떄 초기화된 값을 넘겨주어 기록한다.)

      1. 최초 1을 도는 경우 0인 칸 (안익은 토마토 있는 곳)에 (그 전 칸 + 1)을 기록한다.

      2. 다음번 1에서 도는 경우 이미 0은 처음 시도에서 없어졌기 떄문에 graph[nx][ny] = min(graph[nx][ny], graph[x][y] + 1)으로 더 작은 값으로 갱신해준다.

   3. 모든 토마토가 익을 수 있는 경우, 그래프에서 (가장 큰 값 - 1)이 출력된다. 익을 수 없는 경우 -1이 출력된다.

3. 가장 큰 문제: 1인 칸 (익은 토마토가 있는 칸)을 미리 찾아서 queue에 담아놓지 않고 2중 for문을 돌면서 차례로 bfs를 수행한다.

4. 해결: 미리 2중 for문에서 1인 칸 x, y를 queue에 넣고, bfs는 queue에 1인 좌표를 미리 담아두고 parameter없이 그냥 호출한다. 이런 경우 visited도 필요없이, 1인 좌표들에서 모두 동시에 bfs를 수행하기 때문에 더 효율적이다.

해결 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= M:
                continue
            if graph[nx][ny] == 0: 
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))


M, N = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(N):
    graph[i].extend(list(map(int, input().split())))

queue = deque()
for x in range(N):
    for y in range(M):
        if graph[x][y] == 1:
            queue.append((x, y))
bfs()

answer = 0
for x in range(N):
    for y in range(M):
        if graph[x][y] == 0:
            print(-1)
            exit(0) # 조건에 안맞는 경우, program을 그냥 종료시킨다.
        answer = max(answer, graph[x][y])

print(answer-1)