85. 백준 7576 번 토마토 Python 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 알고리즘인 BOJ 7576 번 토마토 입니다.

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

7576번: 토마토

 

 

먼저 백준 7576번 Python 정답 코드입니다. 설명은 아래에 작성해놓았습니다.

from collections import deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(M)]
x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

D = deque()

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

while D:
    i, j = D.popleft()
    for d in range(4):
        x = i + x_dir[d]
        y = j + y_dir[d]
        if 0 <= x < M and 0 <= y < N:
            if box[x][y] == 0:
                box[x][y] = box[i][j] + 1
                D.append((x, y))

res = max(map(max, box)) - 1
for i in range(M):
    for j in range(N):
        if box[i][j] == 0:
            res = -1

print(res)

 

토마토가 모두 익을 때 까지의 최소 날짜를 구해야 됩니다.

익은 토마토의 상, 하, 좌 혹은 우에 익지 않은 토마토가 있다면 다음날 주변의 토마토들은 익게 됩니다.

이렇게 모든 토마토가 익을 때 까지 걸리는 최소 날짜를 출력하면 답이 되는데,

토마토가 연결되어 있지 않아 익지 못하는 경우에는 -1을 출력하면 됩니다.

 

그래프 탐색에는 BFS, DFS 두 방식이 있습니다.

여기서 BFS는 그래프의 시작 노드부터 물결처럼 퍼져나가 탐색을 진행하게 됩니다.

따라서 그래프 상 노드와 노드간의 최단거리를 구할 때 BFS는 매우 유용합니다.

 

1. 익은 토마토가 맨 처음 상자 안에 하나가 있다면

익은 토마토 A 의 상, 하, 좌, 우 토마토들이 익게까지 걸리는 날짜는

A가 익기까지 걸린 날짜 + 1일이 됩니다.

 

토마토 A에 의해 익게되는 토마토들은 A가 익기 까지 걸린 시간 + 1 해서 날짜를 저장하고

그 다음 토마토들이 익기까지 걸리는 시간을 순차적으로 계산합니다.

모든 토마토들이 익으면 마지막에 익은 토마토의 날짜가 모든 토마토들이 익는 최소 날짜가 됩니다.

 

 

2. 익은 토마토가 맨 처음 상자 안에 여러개가 있다면?

BFS에서는 queue를 이용해 선입선출 방식으로 탐색하게 되는데 

예를 들어 queue에 익은 토마토 1번과 2번 좌표를 넣어서 초기화 한다면

 

 1번 토마토는 해당 토마토의 주변 토마토를 익게 만들고,

주변 토마토들은 queue의 2번 토마토 뒤의 대기열에 들어갑니다.

2번 토마토가 익게 한 토마토들은 역시 맨 뒤에 줄을 서게 됩니다.

따라서 그래프 상 위치에 상관 없이 익은 토마토가 여러개 있어도

여러 시작 지점에서 물결처럼 익은 토마토들이 퍼져나가

모든 토마토들이 익기위한 최소 날짜 계산이 가능해집니다.

 

위의 직관으로 파이썬 코드를 구현 해봅시다.

 

상자와 토마토의 위치를 초기화 합니다.

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

 

BFS에 활용할 queue D를 선언하고, 익은 토마토들은 D의 대기열에 입력합니다.

D = deque()

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

 

queue D안에 방문할 좌표가 있다면 (익게 만들 토마토가 있다면)

즉 모든 토마토가 익고 나면 while문이 종료가 됩니다.

방문하여 좌표를 입력받고, 그 다음에 방문할 토마토들 (아직 익지 않은 토마토들)이 있는지 확인한 후

만약 있다면 해당 좌표를 queue 안에 넣고, 동시에 해당 토마토가 익게 될 때 까지의 날짜를 저장합니다.

(숙주 토마토가 익게될 때 까지의 날짜 + 1)

while D:
    i, j = D.popleft()
    for d in range(4):
        x = i + x_dir[d]
        y = j + y_dir[d]
        if 0 <= x < M and 0 <= y < N:
            if box[x][y] == 0:
                box[x][y] = box[i][j] + 1
                D.append((x, y))

 

모든 토마토가 익게 될 날짜는 box의 마지막 토마토가 익은 날짜가 되겠죠

시작 노드가 1부터 시작했으므로 (0일 일때 익어있는데 1로 시작함)

마지막 토마토가 익은 날짜

즉 box안의 가장 큰 수 - 1이 모든 토마토가 익게 된 날짜가 됩니다.

이것을 변수 res 저장합니다.

만약 box의 모든 노드를 탐색하여 여기서 익지 않은 토마토가 있다면 날짜를 -1로 만들고

res = max(map(max, box)) - 1
for i in range(M):
    for j in range(N):
        if box[i][j] == 0:
            res = -1

 

res를 출력하면 됩니다.

print(res)

 

백준 7576 번 토마토 최종 Python 코드입니다.

from collections import deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(M)]
x_dir = [1, -1, 0, 0]
y_dir = [0, 0, 1, -1]

D = deque()

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

while D:
    i, j = D.popleft()
    for d in range(4):
        x = i + x_dir[d]
        y = j + y_dir[d]
        if 0 <= x < M and 0 <= y < N:
            if box[x][y] == 0:
                box[x][y] = box[i][j] + 1
                D.append((x, y))

res = max(map(max, box)) - 1
for i in range(M):
    for j in range(N):
        if box[i][j] == 0:
            res = -1

print(res)

 

백준 7576 번 토마토 자세한 설명과 Python 코드였습니다.

 

+ 생각해보니 x, y 좌표를 선언하고 while문이 끝난 후 출력하면

queue의 마지막 좌표가 저장이 되므로 graph 내의 최대값을 찾을 필요 없이

바로 최대값의 좌표를 얻을 수 있겠네요

x = y = 0

while D:
    x, y = D.popleft()
    for d in range(4):
        nx = x + x_dir[d]
        ny = y + y_dir[d]
        if 0 <= nx < M and 0 <= ny < N:
            if box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                D.append((nx, ny))

res = box[x][y] - 1
for i in range(M):
    for j in range(N):
        if box[i][j] == 0:
            res = -1
            break

print(res)

감사합니다.