[백준] 7576번 - 토마토 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/7576

7576번: 토마토

토마토 문제는 처음에는 얼마 안 걸릴 줄 알았던 문제이다.

하지만 "시간 초과"라는 결과를 받으면서 해결하는데 꽤 오랜 시간이 걸렸었다.

 

우선 토마토가 인접한 토마토들을 익게 하기 때문에 BFS를 이용해 그래프 순회를 해야겠다고 생각했다.

주어진 그림도 그래프를 의미하고 있다고 생각했기 때문이다.

 

먼저 BFS를 이용해 범위를 벗어나거나 토마토가 없는 곳, 이미 익은 곳은 무시하고 지나가도록 했다.

만약 아직 익지 않은 토마토가 존재하는 곳이라면 순회를 했다.

큐에 토마토의 위치를 추가하고 현재까지 걸린 날짜에 1을 더한 값을 넣었다.

날짜가 지날수록, BFS를 수행할수록 얼마나 걸리는지를 알기 위함이었다.

 

예를 들어,

1 0 1 0 1

0 1 0 1 0

1 0 1 0 1

0 1 0 1 0

1 0 1 0 1

이런 그래프가 있다면

토마토가 익는 현상, BFS의 시작은 항상 익은 토마토이기 때문에 1에서 출발한다.

이 경우에 만약 하루만에 모든 토마토가 익는 것이 끝이 난다면 2가 들어간다.

항상 걸리는 날짜에 비해 결과가 1이 크기 때문에 마지막에 출력하기 전에 1을 줄여줬다.

 

여기서 이전의 DFS, BFS 문제들과 유사하지만 다른 점은

시작 점이 하나가 아니라는 것이다.

다른 문제들의 경우 보통 하나의 정점에서 출발해서 DFS나 BFS를 수행하면 됐지만

이 문제의 경우에는 그래프에 존재하는 모든 1에서 그래프 순회가 동시에 출발해야했다.

어느 토마토부터 익는 것이 아니라 1인 점들은 모두 익기 시작하는 것이다.

이 경우에는 최대값을 구하면 해결되는 문제였다.

 

그래프에서 익을 수 있는 토마토가 모두 익기 위해서는 마지막 토마토가 익는 시간이

최소로 필요한 시간이다.

 

BFS의 시작점을 정할 때 모든 위치 중에서 정점의 값이 1인 위치, 최초의 익은 토마토가 존재하는 곳에서만 출발했다.

최초에 BFS를 진행할 때 입력받은 그래프에서 1을 갖는 위치만 모두 삽입한 이후에 BFS를 진행하면 됐다.

 

왜냐하면 최초의 그래프에서 1이 아닌 위치, 토마토가 없는 -1이나 아직 익지 않은 토마토가 있는 0의 경우에

그 위치에서 시작할 필요가 없기 때문이다. 익는 현상은 무조건 익은 토마토로부터 시작된다.

 

그래프에서 1을 갖는 위치를 큐에 모두 집어넣고 BFS를 수행했다.

그래프에 대해 BFS가 끝나면 그래프의 값들 중에서 가장 큰 값을 구했다.

그 값이 모든 토마토가 익기 위해 필요한 최소 날짜였다.

 

만약에 BFS가 끝난 이후에도 그래프에서 0이 발견된다면 이것은 익을 수 없는 토마토를 의미하기 때문에

-1을 출력했다.

 

[소스코드]

from collections import deque
import sys

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

graph = []
queue = deque()

for i in range(m):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

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


def bfs(y, x):
    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[ny][nx] == -1:
            continue
        if graph[ny][nx] == 0:
            queue.append([ny, nx])
            graph[ny][nx] = graph[y][x] + 1


result = 0

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

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

result = max(map(max, graph)) - 1

for i in range(m):
    if graph[i].count(0) > 0:
        result = -1
        break

print(result)

처음에는 최초의 그래프에서 1을 가지는 위치를 모두 넣고 거기서만 BFS를 수행할 생각을 하지 못했었다.

시간 초과라는 결과를 받고 나서 수정해서 제출했다.

 

하지만 위와 같이 생각해서 문제를 풀었는데도 계속 "시간 초과"라는 결과가 나와서 오랜 시간 고민했었다.

어디에서 시간을 줄일 수 있을지 고민했지만 도저히 찾을 수 없었다.

 

혹시나 하는 마음에 입력을 받는 부분에서 "input()" 대신 "sys.stdin.readline().rstrip()"을 사용했다.

 

설마했는데 원인이 진짜 입력이었다.

생각보다 input()과 readline() 함수 간의 시간 차가 큰 것을 느낄 수 있었다.

 

다음부터는 시간 초과 이슈가 발생하면 꼭 알고리즘만의 문제가 아닌

사소한 문제들도 의심해봐야겠다.