[백준] Python 7576번 토마토 골드5 - 그래프

문제 : https://www.acmicpc.net/problem/7576
분류 : 그래프, 너비 우선 탐색(BFS)

접근

1. 동서남북으로 움직여 토마토를 모두 익게 해야한다.

2. 

   다음과 같이 전염되는 형태로 토마토가 익어나간다.
   

슈도코드

graph에서 1인 곳을 찾아
BFS()

BFS():
  동서남북 변수 저장
  q에 처음 값 삽입(graph에서 1인 곳의 위치)
  
  while queue:
    y, x = 위치(pop)
    
    for 동서남북:
      이동할 곳y = 현재y에서 동서남북
      이동할 곳x = 현재x에서 동서남북
      
      박스 밖으로 나가지 않고, 음수아닌데:
        이동한 곳yx가 0이면 감염시켜야함:
          이동한 곳 = 현재 있는 곳 + 1
          q에 삽입
        
-1는 예외처리 해주고
그래프에 있는 값 중 가장 큰 값이 토마토가 익은 최소 날짜

풀이

from collections import deque

def solution():
    answer = []
    M, N = map(int, input().split()) # 가로, 세로
    matrix = [list(map(int, input().split())) for _ in range(N)] # 토마토 받아서 넣기

    start_position = deque() # 토마토가 있는 곳
    res = 0

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

    BFS(N, M, matrix, start_position)

    for i in matrix:
        for j in i:
            if j == 0:
                print(-1)
                exit(0)
        res = max(res, max(i))
        
    print(res - 1)

def BFS(y, x, graph, start_position:deque):
    # 큐 생성
    queue = start_position
    # 동 서 남 북
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    # 큐가 빌 떄 까지
    while queue:
        # 현재 y, x 큐에서 꺼냄
        cur_y, cur_x = queue.popleft()
        # 방문 처리
        for k in range(4):
            # 동 서 남 북 으로 이동
            next_y = cur_y + dy[k]
            next_x = cur_x + dx[k]

            # 밖으로 나가지 않고 N,M보다 크지 않을 때
            if next_y >= 0 and next_x >= 0 and next_y < y and next_x < x:
                # 해당 값이 0일 때
                if graph[next_y][next_x] == 0:
                    # 인접한 노드는 가중치 증가
                    graph[next_y][next_x] = graph[cur_y][cur_x] + 1
                    queue.append((next_y, next_x))

solution()