백준 7576 토마토 BFS (파이썬)

아이디어

1. 시작점이 여러개인 bfs탐색을 활용해야겠다. (독가스가 퍼지는 상황과 비슷하다.)
2. visited에 시작점으로 부터의 거리를 넣어놓자.

 

---

풀이

import sys
from collections import deque

def bfs(N, M):          # 여러개의 시작점을 갖는 bfs, 시작점에서의 거리를 탐색하며 알아냄
    for i in range(N):
        for j in range(M):
            if tomato[i][j] == 1:
                Q.append((i, j))

    while Q:
        i, j = Q.popleft()
        for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            nr, nc = i + di, j + dj
            if 0 <= nr < N and 0 <= nc < M:
                if tomato[nr][nc] == 0 and visited[nr][nc] == 0:
                    Q.append((nr, nc))
                    visited[nr][nc] = visited[i][j] + 1

def result(N, M):           # 안익은 토마토가 있는지 확인하는 함수
    for i in range(N):
        for j in range(M):
            if tomato[i][j] == 0:
                if visited[i][j] == 0:
                    return print(-1)
    ans = 0
    for i in range(N):
        for j in range(M):
            if visited[i][j] > ans:
                ans = visited[i][j]
    return print(ans)

M, N = map(int, sys.stdin.readline().split())

tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

Q = deque()
visited = [[0]*M for _ in range(N)]
bfs(N, M)

result(N, M)

 

---

후기 및 해설

1. 가스가 퍼지는 상황의 bfs탐색 기법을 배워서 그 코드를 그대로 가져다 쓰면 됐다.
2. 거기에, 안익은 토마토가 있는 경우를 알아내야 해서 result라는 함수를 만들어, 초기 토마토 배열인 tomato가 0이고, visited또한 0이라면 안익은 토마토가 생긴다.