[Backjoon] 토마토

그래프 탐색문제에서는 어떤 방식으로 탐색해야 문제를 빠르게 풀 수 있을지 판단하는 것이 문제의 관건이다. 7576번 토마토 문제는 DFS보다 BFS로 푸는 것이 좀 더 빠르고 쉽게 해결할 수 있는 방법이었다. 문제의 핵심은 그래프를 탐색하기 전에 탐색을 해야하는 위치를 미리 큐에 넣어두고 탐색을 시작하는 것이다. 아래는 파이썬 풀이이다.

 

import sys
from collections import deque

answer = 0

def print_table(tomato_table):
    print()
    for row in range(row_count):
        for col in range(col_count):
            print(tomato_table[row][col], end=" ")
        print()  

def bfs(tomato_positions, day, tomato_table, days):
    q = deque(tomato_positions)
    
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    while q:
        r, c = q.popleft()
        tomato_table[r][c] = 1

        global answer
        answer = max(answer, days[r][c])

        for idx in range(4):
            row_next = r + dy[idx]
            col_next = c + dx[idx]

            if 0 <= row_next < len(tomato_table) and 0 <= col_next < len(tomato_table[0]) and tomato_table[row_next][col_next] == 0 and days[r][c] > days[row_next][col_next]:
                days[row_next][col_next] = days[r][c] + 1
                q.append([row_next, col_next])


if __name__ == "__main__":
    col_count, row_count = list(map(int, sys.stdin.readline().split(" ")))

    tomato_table = []
    for _ in range(row_count):
        tomato_table.append(list(map(int, sys.stdin.readline().split(" "))))

    days = [[-1 for _ in range(col_count)] for _ in range(row_count)]

    # 토마토의 위치 저장
    tomato_positions = []
    for row in range(row_count):
        for col in range(col_count):
            if tomato_table[row][col] == 1:
                tomato_positions.append([row, col])
                days[row][col] = 0

    bfs(tomato_positions, 0, tomato_table, days)
                
    # 익지 않은 토마토 탐색
    for row in range(row_count):
        for col in range(col_count):
            if tomato_table[row][col] == 0:
                print(-1)
                quit()

    print(answer)

 

또한 방문처리만을 위한 배열을 사용하지 않을 때에는 중복방문에 주의해야한다. 위의 소스에서는 days라는 배열에 토마토가 익기까지의 날짜를 기록하고 있는데, 토마토의 위치를 저장할 때 날짜를 0으로 세팅해줘야 중복방문 문제를 해결할 수 있다.