백준 7576 : 토마토 (그래프 탐색)

그래프 탐색 문제이다. 결국 주어진 그래프를 끝까지 탐색하고 해당 그래프 탐색의 마지막 레벨을 구하면 된다.
주어진 그래프에서 1인 위치에서 시작하면 된다. 여기에서 1인 위치는 여러 곳에 존재 할 수 있다.
그렇기 때문에 dfs를 사용하기는 옳지 않다. 루트가 양 끝에 각각 존재하고 중간에서 만나는 경우를 생각하면 이해가 될 것이다.

그래서 queue 자료구조를 사용해 bfs로 풀어주자. 처음 queue에 주어진 root를 모두 넣어주면 알아서 탐색된다.

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



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

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

"""

from collections import deque

M, N = 6, 4
ground = [[1,-1,0,0,0,0],
          [0,-1,0,0,0,0],
          [0,0,0,0,-1,0],
          [0,0,0,0,-1,1]]

roots = [(0, 0), (N-1, M-1)]
def f():
    move = [(1,0),(-1,0),(0,-1),(0,1)]
    queue = deque(roots)

    while queue :
        now = queue.popleft()
        x, y = now
        for m in move:
            dx, dy = m
            nx, ny = x + dx, y + dy
            if 0<=nx<N and 0<=ny<M and ground[nx][ny] == 0:
                ground[nx][ny] = ground[x][y] + 1
                queue.append((nx, ny))

f()
temp = 0
for g in ground :
    temp = max(max(g), temp)
print(temp-1)