기본적으로 bfs를 이용해서 해결할 수 있는 문제이다.
몇 가지 주의해야 할 점을 나열해보자면
처음에 짠 코드는 다음과 같다.
import sys
from collections import deque
def bfs(graph, pos):
q = deque([(p[0], p[1]) for p in pos])
move = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while q:
x, y = q.popleft()
for i in range(4):
nx = x + move[i][0]
ny = y + move[i][1]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if graph[ny][nx] == -1:
continue
if graph[ny][nx] == 0:
graph[ny][nx] = graph[y][x] + 1
q.append((nx, ny))
return max(max(graph)) - 1
m, n = map(int, input().split())
tomatoes = []
for _ in range(n):
tomatoes.append(list(map(int, input().split())))
ripe_tomatoes = [(x, y) for y in range(n) for x in range(m) if tomatoes[y][x] == 1]
days = bfs(tomatoes, ripe_tomatoes)
if [0 for y in range(n) for x in range(m) if tomatoes[y][x] == 0]:
print(-1)
else:
print(days)
문제에 주어진 예제는 모두 만족하였지만 제출 시 오답으로 나왔다.
deque
를 사용해 시간 제한도 만족할 수 있었고 기본적인 bfs로 모든 토마토를 익힐 때까지 며칠이 걸리는지도 구할 수 있었다.
또 bfs가 완료된 후 graph 내에 0이 하나라도 있으면(즉 모든 토마토를 익게 할 수 없다면) '-1'을 반환하도록 만들기도 했다.
즉 로직 상에 문제는 없다고 판단했는데 어디서 틀렸는지 알 수 없었다.
반례를 찾아보던 중 문제점을 찾아낼 수 있었다.
2차원 배열에 대해 max를 수행하면 '첫번째 원소가 max인' 1차원 배열을 출력한다. 때문에 의도한 바대로 graph 내에서 가장 큰 값을 반환하도록 하려면 max(max(graph)) - 1
을 max([max(row) for row in graph])
로 바꿔야 한다.
최종 정답 코드는 다음과 같다.
import sys
from collections import deque
def bfs(graph, pos):
q = deque([(p[0], p[1]) for p in pos])
move = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while q:
x, y = q.popleft()
for i in range(4):
nx = x + move[i][0]
ny = y + move[i][1]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if graph[ny][nx] == -1:
continue
if graph[ny][nx] == 0:
graph[ny][nx] = graph[y][x] + 1
q.append((nx, ny))
return max([max(row) for row in graph]) - 1
m, n = map(int, input().split())
tomatoes = []
for _ in range(n):
tomatoes.append(list(map(int, input().split())))
ripe_tomatoes = [(x, y) for y in range(n) for x in range(m) if tomatoes[y][x] == 1]
days = bfs(tomatoes, ripe_tomatoes)
if [0 for y in range(n) for x in range(m) if tomatoes[y][x] == 0]:
print(-1)
else:
print(days)