백준 7576 파이썬 문제 풀이: 토마토

백준 7576 파이썬 문제 풀이 : 토마토

 

문제 링크 

7576번: 토마토

---

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

입출력 예시

 

 

풀이

문제에서 '최소일 수', '인접한 곳에 영향을 준다.'라고 나와 있어서 BFS를 선택하였다.

 

기존 BFS의 경우 방문 했는지 여부를 판단하는 문제였다면, 이번 문제는 바이러스처럼 퍼져나가는 문제로 최소 일수를 구하는 문제였다. 기존의 문제대로 풀이를 하니 방문하는 노드 수만큼 결과가 나와서 이 부분을 어떻게 해결하냐가 중요한 포인트였다.

 

방문처리 하는 과정에서 0을 1로 바꾸는 게 아니라 현재 노드에 +1을 해주면서 진행하였다.

자세히 설명하자면,

1. 다음에 방문할 노드가 그래프의 범위 안에 있는지 판단

2. 다음에 방문할 노드가 0 인지 판단

3. 현재 노드에 +1을 한 값을 다음 노드에 삽입

4. 방문할 노드가 없을 때까지 반복

 

예제 1번을 예로 들어서 표현하자면 "더 보기"의 사진처럼 진행된다.

 

따라서,

graph[nx][ny] = graph[x][y] + 1

이 코드가 중요한 코드였다.

 

추가적으로 기존의 코드에서 deque는 dfs안에서 정의하였는데, 이 문제의 경우 출발하는 노드의 지점이 2개가 될 수 있기 때문에 전역변수로 지정해서 입력 받을때 1인 값들의 좌표를 deque에 우선 저장한다음 bfs를 진행하는것도 하나의 핵심이였던 것 같다. 

 

제출 코드

from collections import deque

M, N = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(N)]
queue = deque([])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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 graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

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

bfs()
res = 0
for i in range(N):
    for j in range(M):
        res = max(res, graph[i][j] - 1)
        if graph[i][j] == 0:
            res = -1
            print(res)
            exit(0)

print(res)