[python] 백준 7576번: 토마토(BFS)

#  7576 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque

M, N = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(N)]

dx, dy = [0,0,-1,1], [-1,1,0,0]
queue = deque()
def bfs():
    
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < N and 0 <= ny < M and boxes[nx][ny] == 0:
                boxes[nx][ny] = boxes[x][y] + 1 
                queue.append((nx,ny))

for i in range(N):
    for j in range(M):
        if boxes[i][j] == 1:
            queue.append((i,j))

bfs()
answer = 0
for line in boxes:
    for tomato in line:
        if tomato == 0:
            print(-1)
            exit(0)
    answer = max(answer, max(line))

print(answer - 1)

📝 풀이

4방향을 탐색하면서 익은 토마토(1)이 있다면 인접한 위치에 있는 안익은 토마토(0)가 하루가 지날때마다 익은 토마토가 되는 문제이다. 구현은 어렵지 않았지만 출력 과정에서 조건들이 붙어서 까다로운 문제였다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

from collections import deque

M, N = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(N)]

dx, dy = [0,0,-1,1], [-1,1,0,0]
queue = deque()

먼저 bfs를 실행하기 위해 deque 라이브러리를 불러와주고 토마토를 담을 boxes를 생성해준다.

방향 탐색을 위한 dx, dy와 queue를 생성해준다.

def bfs():
    
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if 0 <= nx < N and 0 <= ny < M and boxes[nx][ny] == 0:
                boxes[nx][ny] = boxes[x][y] + 1 # 익은 토마토 바뀌는 시간 저장
                queue.append((nx,ny))

일반적인 bfs와 마찬가지로 queue가 빌때까지 while문을 실행시켜주고, 4방향을 탐색하면서 익은 토마토 주변이 안익은 토마토라면 해당 위치에 익은 토마토가 되기까지 시간을 기록해주고 좌표를 queue에 삽입시켜준다.

answer = 0
for i in range(N): # 1번
    for j in range(M):
        if boxes[i][j] == 1:
            queue.append((i,j))

bfs() # 2번

# 3번
# boxes
# [[9, 8, 7, 6, 5, 4], [8, 7, 6, 5, 4, 3], [7, 6, 5, 4, 3, 2], [6, 5, 4, 3, 2, 1]]

for line in boxes: 
    for tomato in line:
        if tomato == 0:
            print(-1)
            exit(0)
    answer = max(answer, max(line)) # 4번

print(answer - 1) # 5번

# 1번에서 boxes들을 탐색하면서 익은 토마토의 좌표를 queue에 삽입시켜준다.

 

# 2번에서 bfs를 실행시켜서 좌표에 들어있는 값들을 탐색한다. bfs를 돌면서 좌표값 주변을 탐색한다.

 

# 3번

테스트 케이스 1번을 input값으로 넣었을 때 boxes는 3번과 같다. 이중 리스트를 벗기기 위해 이중 포문을 돌려주면서 tomato가 0이라면 익지 않은 토마토가 있다는 뜻이므로 print(-1)을 해주고 exit()를 해준다.

 

# 4번

tomato가 0인것이 없다면 line중에서 제일 큰 값과 answer값을 비교하면서 answer값을 갱신시켜준다. answer의 초기 값이 0이므로 처음 반복문을 실행하면 line의 값이 answer에 저장되게 된다.

 

# 5번

익은 토마토(1)을 기준으로 숫자를 증가시켜주었으므로 최종적으로 걸린 시간을 출력할때에는 -1을 해준다.

가장 오래 걸린 시간의 -1을 해주면 정답이 된다.