백준 7576 파이썬(BFS)

최단거리를 묻는 문제에서는 우선 BFS탐색법을 생각해봐야 한다.

단순히 최단거리를 묻는 문제가 아니라

여러가지 조건들을 만족시켜야 하는 상황이어서

코드가 약간 길어지긴 했지만

다행히 통과가 되었다.

 

<꼭 기억하자>

BFS문제는 큐 자료구조를 이용해서 큐가 빌때까지 하나씩 노드를 뽑아서 탐색하는 방법이다

1. 큐 자료구조를 만들고

2. 큐에서 한개씩 뽑아서 탐색

3. 큐가 빌때까지(while queue:)

 

코드 

# 7576 토마토

m,n = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우

from collections import deque
def bfs_tomato(m,n,graph,cnt=0):

    # 모든 토마토가 이미 채워져 있는 경우
    test = set()
    for x in range(n):
        for y in range(m):
            test.add(graph[x][y])
    if 0 not in test:
        return 0
    
    queue = deque()
    
    for x in range(n):
        for y in range(m):
            if graph[x][y] == 1:
                queue.append([x,y])
          
    while queue:
        cnt += 1
        for _ in range(len(queue)):
            tomato = queue.popleft()
            for i in arrow:
                new = [x+y for x,y in zip(tomato,i)]
                if new[0] < 0 or new[0] > n-1 or new[1] < 0 or new[1] > m-1:
                    continue
                if graph[new[0]][new[1]] == 0:
                    queue.append(new)
                    graph[new[0]][new[1]] = 1
        # print(f'queue:{queue},count:{cnt}') 중간중간 확인용
     
    for x in range(n):
        for y in range(m):
            if not bool(graph[x][y]):
                return -1
    return cnt-1

print(bfs_tomato(m,n,graph))