문제
출처: 백준 - 토마토 : 7576번
풀이
BFS 넓이 우선탐색 문제다.
1. BFS는 큐 자료형을 쓰는 것이 일반적이므로 큐를 불러온다. 그리고 상하좌우 탐색을 위해 좌표를 생성하고, 문제에서 제시하는 대로 가로, 세로의 길이만큼의 토마토 창고를 2차원 배열을 만든다. 그리고 토마토 창고와 같은 크기의 토마토가 익은 날짜를 담을 2차원 배열도 하나 만든다.
2. 토마토가 익은 것이 있는지 탐색을 진행하고 익은 토마토가 있으면 그 좌표를 큐에 담는다. 익은 토마토를 중심으로 상하좌우 탐색하며 날짜를 계산해야 하기에 날짜를 담을 2차원 배열은 모두 0으로 초기화가 되어 있어야 한다.
3. 토마토가 익은 1의 자리부터 큐에서 꺼내서 상하좌우를 탐색하는데, 탐색 조건은 2차원 배열을 벗어나지 않아아 하며 익지 않은 토마토의 자리만 확인해야 하기에 토마토 창고의 값이 0일 때에만 방문하도록 한다. 그리고 방문 했다면 익은 토마토이기 때문에 0을 1로 바꿔줘서 재방문하지 않도록 해준다. 그리고 그 자리에 같은 좌표 값으로 날짜를 담을 2차원 배열에 시작점에서 +1을 해줘서 날짜를 계산하도록 한다. +1은 현재의 날짜에서 하루를 더한 의미다. 그리고 그 익은 토마토의 좌표를 큐에 담아서 그 곳에서부터 다시 범위 탐색을 하도록 한다.
4. 3번으로 모든 탐색이 끝난 후, 익지 않은 사과, 즉 0이 있다면 방문하지 못한 경우이므로 -1을 반환하도록 한다.
5. 3번으로 모든 탐색이 끝난 후, 익지 않은 사과, 즉 0이 없다면 날짜를 체크한 2차원 밸열을 탐색하여 가장 높은 수를 반환한다. 가장 높은 수가 바로 모든 토마토가 익은 날짜이다.
6. flag 변수를 하나 지정하여 마지막에 4번과 5번을 비교하여 -1 아니면 날짜를 최종 반환하도록 한다.
코드
from collections import deque
dQ = deque() # 큐 자료형 만들기
dx = [0, 1, 0, -1] # 상하좌우 탐색 범위 생성
dy = [-1, 0, 1, 0]
m, n = map(int, input().split()) # 가로, 세로 길이 입력
board = [list(map(int, input().split())) for _ in range(n)] # 가로, 세로 길이에 따른 토마토 창고 입력
day = [[0] * m for _ in range(n)] # 토마토 창고와 같은 크기의 날짜 2차원 배열 생성
# 익은 토마토를 찾아서 그 좌표를 큐에 담도록 한다.
for i in range(n):
for j in range(m):
if board[i][j] == 1:
dQ.append((i, j)) # 이 좌표가 시작점
# 큐에서 하나씩 빼서 상하좌우 넓이 우선탐색을 진행한다.
while dQ:
x, y = dQ.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 창고의 크기를 벗어나지 않도록, 익지 않은 토마토만 방문하도록
if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
board[nx][ny] = 1
day[nx][ny] = day[x][y] + 1
dQ.append((nx, ny))
flag = 0
maxN = -1e9
# 익지 않은 경우
for a in range(n):
for b in range(m):
if board[a][b] == 0:
flag = 1
# 모두 익은 경우
for a in range(n):
for b in range(m):
if day[a][b] > maxN:
maxN = day[a][b]
# 익지 않은 경우와 익은 경우를 flag 변수를 통해서 확인
if flag == 0:
print(maxN)
else:
print(-1)