https://www.acmicpc.net/problem/7576
당분간 BFS, DFS 문제를 풀 생각이다.
이 문제는 BFS 시작점이 여러 개이다.
시작점이 여러 개인 BFS
시작점을 한 개씩 BFS 실행하면?
예를 들어서 상자 상태가
0 0 0
0 1 0
1 0 0 이면
(1, 1)을 BFS 실행하고 이후에
(2, 0)을 BFS 실행하는 것이다.
그러나, 이렇게 하면 최종 날짜를 구하는 방식이 복잡해지고,
BFS의 시간복잡도는 O(NxM) 이므로 익은 토마토가 가장 많은 경우인 NxM개 일때,
총 시간복잡도는 O((NxM)^2)가 된다. 상당한 시간이 걸릴 수 있다.
어떻게 하면 좋을까?
시작점을 BFS 실행 전에 Queue에 집어넣는다.
상자 입력이 완료되면 인덱스를 하나씩 검사해서 익은 토마토(1)일 때, Queue에 넣는다. BFS 특성 상 나중에 Queue에 들어온 인덱스에 대한 날짜는 이전에 들어온 인덱스에 대한 날짜보다 크거나 같은 값을 가지게 되어 있다. 나중에 검사되었기 때문에 당연한 결과이다.
이렇게 Queue에 한번에 넣은 후에 BFS를 실행하면 시간을 단축할 수 있다.
이제 구현을 해보자.
구현
BFS에서 Queue에 넣을 대상은 안 익은 토마토이다.
따라서, 안 익은 토마토와 (익은 토마토와 빈칸)을 구분지어야 한다.
구분짓는 방법은 안 익은 토마토의 날짜를 -1로 하는 것이다.
그리고, Queue에 들어갈 조건은 날짜가 0보다 작은 값을 가지는 것이다. 즉, 안 익은 토마토만 넣게 되는 것이다.
조심해야 할 것은 날짜가 반드시 0보다 작아야 한다. 0보다 작거나 같다고 설정하면 빈칸이나 익은 토마토도 방문한다.
이것 때문에 계속 '틀렸습니다' 결과를 받았다.
NOTE
Queue에 들어갈 대상이 무엇인지,
들어갈 대상과 들어가면 안 되는 대상을 구분짓는 방법이 무엇인지,
Queue에 들어가면 어떤 효과를 부여해야 하는지 (이 문제에서는 날짜를 갱신하는 것)
잘 생각해보는게 좋겠다.
CODE
import sys
from collections import deque
m, n = map(int, input().split())
box = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
day = [[0] * m for _ in range(n)]
dx = [0, 0, -1, 1] # E,W,S,N
dy = [1, -1, 0, 0]
def how_long(arr: list):
queue = deque([])
# 익은 토마토 고르기 COLLECT 1
for i in range(n):
for j in range(m):
if arr[i][j] == 1:
queue.append([i, j])
# 안 익은 토마토는 날짜를 -1로 변경
elif arr[i][j] == 0:
day[i][j] = -1
# start BFS
while queue:
cur_x, cur_y = queue.popleft()
for k in range(4):
next_x = cur_x + dx[k]
next_y = cur_y + dy[k]
# 배열 범위 밖
# 인접한 인덱스의 날짜가 0이상일 때, 즉, 안 익은 토마토가 아닐 때 무시
if next_x < 0 or next_x >= n or next_y < 0 or next_y >= m or day[next_x][next_y] >= 0:
continue
# 안 익은 토마토의 날짜 변경
queue.append([next_x, next_y])
day[next_x][next_y] = day[cur_x][cur_y] + 1
# 날짜 최대값 구하기
max_day = 0
for p in range(n):
for q in range(m):
# 안 익은 토마토가 있다면 -1
if day[p][q] == -1:
return -1
# 최대값 갱신
if day[p][q] > max_day:
max_day = day[p][q]
return max_day
print(how_long(box))
