[Python]Baekjoon 7576번: 토마토(BFS)

1. 문제

 

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

7576번: 토마토

 

N, M 개의 칸에 토마토가 들어있다.

 

0은 익지 않은 토마토, 1은 익은 토마토, -1은 빈칸을 의미한다.

 

익은 토마토와 인접해 있는(상, 하, 좌, 우) 토마토는 하루가 지나면 익는다.

 

토마토가 모두 익는데 며칠이 걸릴까?

 

2. 풀이

지금까지 익숙하게 풀어왔던 BFS에 조금 더 생각을 해야 하는 문제였다.

 

가장 핵심적인 부분은 BFS의 시작 지점이 여러 개인데 이를 어떻게 처리해 주는가였다.

 

이 부분을 처리해주기 위해 BFS를 돌리기 전에 반복문을 통해 시작점을 미리 판단해서 큐에 넣어준다.

 

그리고 이 큐를 BFS에 전달해 탐색을 진행한다.

 

그렇지 않으면 첫 번째 시작점을 돌 때 모두 방문처리가 되기 때문에 두 번째 시작점에서는 BFS를 돌지 않게 된다.

 

시작점이 한개인 경우에는 기존의 풀이방식대로 하면 되겠지만, 시작점이 두 개인 경우 기존의 방식으로 풀이하면 두 시작점에서 출발한 토마토가 만날 때 탐색이 종료되어야 하는데 그렇지 못하고 한 시작점에서 끝까지 탐색하고 다른 시작점에서는 시작도 못하게 된다.

 

익지 않은 토마토가 있는지를 판단하는 부분도 고려가 필요했는데, 방문 처리가 되지 않았으면서 이 토마토가 익은 토마토가 아니고 빈칸이 아니여야 익지 않은 토마토가 있는 것으로 처리해야 한다.

 

그렇지 않고 방문 처리만을 기준으로 판단하면 빈칸에 둘러싸여 있는 빈칸과 같은 경우도 익지 않은 토마토로 판단하기 때문에 익지 않은 토마토가 없음에도 빈칸을 익지 않은 토마토로 판단하여 -1을 출력하게 된다.

3. 코드

 

from collections import deque

import sys

input = sys.stdin.readline

M, N = map(int, input().split())

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

visited = [[-1] * M for _ in range(N)]

start = []

dx = [-1, 1, 0, 0]

dy = [0, 0, -1, 1]

def bfs(queue):

    while queue:

        x, y = queue.popleft()

       

        for i in range(4):

            nx, ny = dx[i] + x, dy[i] + y

           

            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == -1:

                if graph[nx][ny] == 1:

                    visited[nx][ny] = 0

                elif graph[nx][ny] == -1:

                    visited[nx][ny] = 0

                elif graph[nx][ny] == 0:

                    visited[nx][ny] = visited[x][y] + 1

                    queue.append((nx,ny))

for i in range(N):

    for j in range(M):

        if graph[i][j] == 1 and visited[i][j] == -1:

            start.append((i, j))

            visited[i][j] = 0

q = deque(start)

bfs(q)

flag = 0

for i in range(N):

    for j in range(M):

        if visited[i][j] == -1 and graph[i][j] != -1 and graph[i][j] != 1:

            print(-1)

            flag = 1

            break

    if flag == 1:

        break

   

max = 0

for i in range(N):

    for j in range(M):

       if max <= visited[i][j]:

           max = visited[i][j]

if flag != 1:

    print(max)

4. 느낀점

시작점이 여러 개인 경우에서 생각이 꼬여서 헤맸는데 신과 같은 친구의 도움으로 나름 빠르게 길을 찾을 수 있었다.

 

그리고 전달받은 queue를 활용할 때 i, j = queue 이런 문법은 없는 문법이다.(지금 생각해 보니 말도 안 됨)

 

x, y = queue.popleft()와 헷갈렸던 것 같은데 이건 queue에서 첫 번째 원소를 빼는 경우니까 말이 되지만 위의 경우는 큐 전체를 때려 박는다는건데 정말 멍청하다.

 

queue 자료구조나 프로그래밍 문법이 아직 익숙하지 않아서 꾸준하게 연습해야 할 것 같다.

 

print를 활용하여 직접 찍어보는 것이 좋은 디버깅 방법이라는 것은 인지하고 있는데

 

막상 문제 상황을 마주하면 익숙하지 않아서 그런지 찍어볼 생각을 못하는 것 같다.

 

친구의 디버깅 과정을 보며 visited를 print 하는 것을 보았고 덕분에 경험치를 조금 더 쌓을 수 있었다.

 

오늘 하루도 쌓였다