❓문제
[골드5]
https://www.acmicpc.net/problem/7576
💭 아이디어
문제에서 최소 일수를 구하라고 했으므로 BFS로 풀 수 있음을 깨달았다.
익은 토마토(1)는 출발점이 된다. 출발점이 여러개인 경우 한 출발점에 대해 BFS를 마친 후 다음 출발점에 대해 BFS를 수행하면 최소일수를 구할 수 없다. 따라서 이 경우 익은 토마토(1)인 위치를 처음에 모두 Queue에 넣어두어야 한다.
최소일수는 탐색할 때마다 그래프 값을 1씩 증가시켜주며 계산한다.
마지막에 그래프 값 중 가장 큰 값이 최소일수가 된다.
❗ 풀이
from collections import deque
import sys
def bfs():
while q:
x, y = q.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] == -1: # 토마토가 있지 않은 칸
continue
if graph[nx][ny] == 0: # 익지 않은 토마토인 칸
graph[nx][ny] = graph[x][y] + 1 # 일수 갱신
q.append((nx, ny))
m, n = map(int, input().split())
graph = []
for _ in range(n):
a = list(map(int, sys.stdin.readline().split()))
graph.append(a)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque()
for i in range(n):
for j in range(m):
if graph[i][j] == 1: # 익은 토마토이면
q.append((i, j))
bfs()
# print(graph)
answer = 0
for i in range(n):
for j in range(m):
if graph[i][j] == 0: # 모든 토마토가 익지 못하는 경우
print(-1)
exit()
if graph[i][j] > answer: # 모든 토마토가 익은 경우 최댓값 -1 이 답
answer = graph[i][j] - 1 # 시작이 0이 아닌 1이었으므로 1 빼기
print(answer)추가 설명
예제 입출력 1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
[9, 8, 7, 6, 5, 4]
[8, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
8위와 같이 BFS를 수행할 때마다 그래프 값을 현재 노드 값 + 1을 해주면 위와 같다.
위 예시가 가장 직관적인 예시 같다.
최소 일수는 9에서 1을 뺀 8이다. (시작이 0이 아닌 1이므로 1을 빼줘야 한다.)
예제 입출력2
6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
[0, -1, 7, 6, 5, 4]
[-1, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
-1예시2는 토마토가 모두 익지 못하는 경우이다. 토마토가 들어있지 않은 칸으로 둘러싸여 (0,0)에 위치한 익지 않은 토마토는 익을 수 없다.
예제 입출력3
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
[1, -1, 7, 6, 5, 4]
[2, -1, 6, 5, 4, 3]
[3, 4, 5, 6, -1, 2]
[4, 5, 6, 7, -1, 1]
6내가 고민했던 예시이다. 동시에 어떻게 진행해야 하는지 고민했는데 모두 Queue에 넣은 후 BFS를 수행하면 됐다.
✅ Comment
내가 고민했던 부분은 한 점에서 출발해 탐색을 마쳐버리면 최소일수를 구할 수 없다는 점이었다.
어떻게 한 점에서 출발해 탐색을 마치기 전에 다른 출발점(익은 토마토 위치)에서 탐색을 수행할 수 있는지 (동시에(번갈아가며) BFS를 수행해야 한다고 생각했다) 고민을 했다. 보통 출발점에서 바로 bfs 함수를 호출해 가능한 곳까지 탐색을 진행하고, 출발지가 남은 경우 그 지점에서 또 bfs 함수를 호출해 탐색을 진행하였다. 이 문제는 출발지가 될 수 있는 즉, 익은 토마토 지점을 모두 Queue에 append 해준다. 이렇게 함으로써 고민한 부분이 해결된다.(번갈아가며 BFS가 수행될 수 있다. queue에 두 출발점 모두 들어있으니!)
이전에 2178번 미로 탈출 문제를 풀었었다. 미로 탈출 문제에서 BFS를 수행할 때마다 현재 노드값 + 1을 해줌으로써 움직여야 하는 최소 칸의 개수를 구했다. 토마토 문제에서도 탐색을 수행할 때마다 하루씩 증가시켜 최소 일수를 구한다.
