[백준] 토마토 [찾지 못한 부분 + 코드 + 해설]

구현 & BFS & 최단경로

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

7576번: 토마토

 

코드

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

m, n = map(int, input().split())

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

def bfs(first_queue):
  
    dx = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    while first_queue:
        q = first_queue.popleft()
        x, y = q[0], q[1]
        
        for idx in range(4):
            nx = dx[idx][0] + x
            ny = dx[idx][1] + y
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m or box[nx][ny] == -1:
                continue
        
            if box[nx][ny] == 0:
                first_queue.append([nx, ny])
                box[nx][ny] = box[x][y] + 1

first_queue = deque([])


for i in range(n):  
    for j in range(m):

        if box[i][j] == 1:
            first_queue.append([i, j])


bfs(first_queue)


cnt = 0
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            cnt += 1
  
if cnt != 0:
    print(-1)
else:
    print(max(map(max, box))-1)

 

설명

 토마토 문제 같은 경우 '익숙한 BFS 구현에서 벗어나게 한 문제라고 표현하고 싶다.' BFS를 구현하는 방법은 그렇게 어렵지 않다. 하지만 BFS를 사용하는 문제를 해석하는 건 너무나 다른 문제다. 위 문제가 위에 bold로 표시되어 있는 부분을 설명해 준다.

 

 BFS의 정의는 생략하고 위 문제의 목적부터 본다면 해당 문제가 풀고자 하는 목표는 익지 않은 토마토가 전부 익을 때까지 걸리는 '최소 일수'를 구하는 문제다. 여기서 최소 일수라는 표현은 가장 단기간에 토마토가 익게 되는 지점을 원하는 것이라고 생각해 볼 수 있다. 결국 최단 경로 문제랑 유사하다고 판단할 수 있다. 왜냐하면 최소 일수 자체가 가장 짧은 구간을 의미하며 이는 여러 개의 경로들 중 가장 짧게 완성될 수 있는 경로를 원하기 때문이다. 왜 '여러 개의 경로들'이라고 표현했냐면 위 문제에서는 아래와 같은 표현을 볼 수 있다.

 

 

"익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다."

 

 

 위 문장을 정확하게 해석해야 된다. 그래서 문장을 이렇게 바꿔보자. '익은 토마토의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받게 된다.' 본래 문장의 이해를 돕기 위해서 작성한 문장이다. 두 문장의 가장 큰 차이점만 보면 토마토들의, 토마토의 라는 표현이다. 본래 문제에 사용된 표현은 토마토들의 인접한 곳이다. 즉 익은 토마토들이 여러 개 있고 그 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 있다는 말이 된다. 따라서 들이라는 거 자체가 복수를 의미하고 있다. 또한 이러한 토마토들은 하루가 지나면 영향을 주게 된다. 따라서 동시 다발적으로 진행되게 된다는 사실을 유추해 볼 수 있는데 사실 이 문장 가지고는 유추하기 조금 힘들었다. 해당 표현을 문제를 읽을 때 크게 관심을 두지 않고 이해하고 넘어갔는데 예제 문제를 보고 깨달았다. 동시다발적으로 진행되지 않는다면 예제의 결과와 다른 결과가 나오게 된다. 여기서 첫 번째 포인트를 잡아야 한다고 말하고 싶다.

 

 두 번째 포인트는 동시다발적으로 진행되게 하려면 어떻게 해야 될까를 생각해 봐야 되는 문제다. 이 문제를 고민하게 된다면 예제 3번 답이 이상하게 나오거나 혹은 정확히 푼 것 같은데 답이 안 나오거나 둘 중 하나라고 생각한다. 이 포인트 때문에 나는 '익숙한 BFS 구현에서 벗어나게 해 준다.'라는 표현을 작성했다. 왜 익숙한 bfs 구현이라고 했을까 익숙한 bfs 구현이라고 한다면 인접한 곳부터 큐에 넣고 방문한다. bfs 동작원리가 그러하기 때문이다. 인접한 곳부터 접근하는 건 틀린 게 아니다. 하지만 동시다발적으로 진행되게 만든 건 아니다. 왜냐하면 한 곳부터 먼저 진행되게 되기 때문이다. 토마토들이 상자에서 멀리 떨어져 있을 때 각기 다른 경로를 가져야 한다. 그렇다는 건 각기 다른 경로를 지나면서 오게 된다는 뜻이 된다. 하지만 익숙한 bfs 구현대로 하게 된다면 익은 사과하나로부터 시작해서 그 주변에 인접한 곳들만 계속 진행되게 된다. 그러면 크게 바라본다면 아래와 같다.

 

 

 '익힌 사과 하나로부터 얻어진 결과'

우리가 원하는 목표는 '익힌 사과들로부터 가장 짧은 경로를 원하는데 말이다.'

 

 

 결국 익힌 사과들로부터의 경로들 중 가장 짧은 경로로 구현해야 맞는 것이 된다. 따라서 우선적으로 큐에 들어가져야 하는 건 BFS 실행할 때 익힌 사과들을 경로선에서 먼저 출발을 시켜주어야 한다. 나도 이 사실을 너무나 가볍게 여기고 구현하여 예제 3번에서만 계속 다른 답이 나와 시간이 많이 걸렸다. 구현 자체가 어려운 것은 아니지만 익숙한 bfs 구현을 외우다시피 하며 구현하게 된다면 해당 포인트를 캐치하기 어렵지 않았을까 생각이 든다.