[백준] 7576번(python 파이썬)

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

 

---

미로 문제와 동일한 문제이다.

하지만 익은 토마토가 여러개 있을경우 그 토마토에 대해서 bfs처리를 동시에 해줘야한다.

처음에는 만약에 익은토마토가 여러개이고 안익은 토마토로 연결되어있으면 익은토마토의 개수만큼 나눠주면 되지아 않을까하고 풀어봤는데 아니었다.

어떻게 동시에 bfs를 돌려야 하는지 고민하는데 쓰레드 밖에 도저히 생각이 나지 않아서 알아본결과 큐에 익은 토마토를 넣어주면 되는 것이었다. 간단한 방법이었지만 생각이 나지 않으면 풀 수 없는 문제..

bfs에서 큐를 왜사용하는지 알아야함

 

---

from collections import deque
import sys
input = sys.stdin.readline

col, row = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(row)]

visited = [[False] * col for _ in range(row)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()

def Bfs(queue, graph, visited):
    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            next_x = pop_x + dx[i]
            next_y = pop_y + dy[i]

            if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
                continue
            if not visited[next_x][next_y] and graph[next_x][next_y] == 0:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = True
                graph[next_x][next_y] = graph[pop_x][pop_y] + 1

zero_flag = False
for i in range(row):
    for j in range(col):
        if graph[i][j] == 1:
            queue.append((i, j))

Bfs(queue, graph, visited)

for i in range(row):
    if 0 in graph[i]:
        zero_flag = True
        break

if not zero_flag:
    print(max(map(max, graph)) - 1)
else:
    print(-1)