문제 😀
전형적인 BFS문제로 인접한 노드들부터 탐색해서 최단 경로(문제에선 최소의 일수)를 구하는 문제이다.
생각 😁
BFS문제이므로 queue를 이용할 생각을 해야한다.
파이썬으로 풀었으므로 deque를 이용함.
- 처음에 익은 토마토들이 있는 위치를 큐에 넣음
- 큐를 하나씩 돌면서 처음에
popleft()한 익은 토마토에 대해서 상하좌우 검사를 하고 적절하면 움직인 위치에 이전위치를 1더한다. - 그러면 결국 마지막으로 방문한 노드의 값이 일수가 되므로 이 일수를 리턴한다. (-1해야한다, 이유는 문제가 그렇게 요구하므로)
코드 😃
python
from collections import deque
M, N = map(int, input().split())
# M은 가로 N은 세로
graph = []
for _ in range(N):
graph.append(list(map(int, input().split())))
tomatoes = deque([])
for i in range(N):
for j in range(M):
if graph[i][j] == 1:
tomatoes.append([i, j])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
days = 0
while tomatoes:
v = tomatoes.popleft()
curX = v[0]
curY = v[1]
for i in range(4):
nx = curX + dx[i]
ny = curY + dy[i]
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue
if graph[nx][ny] == -1:
continue
if graph[nx][ny] == 0:
graph[nx][ny] = graph[curX][curY] + 1
days = graph[nx][ny]
tomatoes.append([nx, ny])
# print('--------------')
# for i in range(N):
# for j in range(M):
# print(graph[i][j], end=' ')
# print('')
# print('------------')
return days - 1
start = False
for i in range(N):
for j in range(M):
if graph[i][j] == 0:
start = True
break
if start == False:
print(0)
else:
result = bfs()
flag = False
for i in range(N):
for j in range(M):
if graph[i][j] == 0:
flag = True # 다익을순 없다.
break
if flag == True:
print(-1)
else:
print(result)
오류난 이유들 🤣
- 익은 토마토들의 위치를 처음에 저장할때 익은 토마토들을 저장할 큐를 여러개 생성함. 즉, 익은토마토가 10개면 큐를 10개생성해서 각 큐에서 동시에 방문을 시작하게 하는걸 꾀했다. 그런데 이럴필요가 없다는걸 느낌. 나는 익은토마토가 여러개면 동시에 독립적으로 출발해야하므로 큐를 여러개 생성해야한다 생각해서 무조건 이게 맞다 생각했는데 익은 토마토들의 위치를 저장한 큐를 하나만 생성해도 풀수있음. 왜냐면 그게 큐이기 때문이다. 먼저 들어온 토마토위치를 pop하면 그다음에 남아있는 토마토 위치는 독립된 익은 토마토의 위치이므로 여러개 큐를 애초에 만들 필요가 없는문제임. 사실 로직은 비슷했으나 이렇게 큐를 하나로 바꾸니 알수없는 오류가 줄어들어서 통과한것같다. (이전에는 알수없는 오류로 통과하지못했다.. 테스트케이스라던지 반례는 모두 통과했는데 정작 틀렸습니다가 뜸..)
