BOJ 7576번 - 토마토

[백준 온라인 저지 링크]

7576번: 토마토

2178번 미로 탐색과 비슷하게 BFS 탐색을 최소화하는 경로를 찾아야 했습니다.

세 번째 케이스 (출발지점이 두곳임)

다만 가장 머리아팠던게 바로 세 번째 케이스로, 출발지점이 둘 이상일 경우에는 아래처럼 토마토를 발견할 때 탐색을 시작하도록 하면 절대 최솟값을 찾을 수 없습니다.

for row in range(N):
    for col in range(M):
        if tomatoes[row][col] == 1 and visited[row][col] == False:
            BFS((row, col)

그래서 가능한 출발점을 미리 계산한 후, 가능한 출발점들을 배열로 한번에 전달함으로써 해결할 수 있었습니다.

for row in range(N):
    for col in range(M):
        if tomatoes[row][col] == 1 and visited[row][col] == False:
            start_nodes.append((row, col)) # start_nodes는 시작점이 될 수 있는 좌표들의 배열
            
BFS(start_nodes)

 

[정답 코드 - Python]

from collections import deque

M, N = map(int, input().split())
tomatoes = []
visited = [[False] * M for _ in range(N)]
start_nodes = []
cnt = 0

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

for i in range(N):
    tomatoes.append(list(map(int, input().split())))


def BFS(start_node_list):
    q = deque()
    for i in start_node_list:
        q.append(i)
    while q:
        y, x = q.popleft()
        visited[y][x] = True
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < M:
                if visited[ny][nx] == False and tomatoes[ny][
                        nx] != -1 and tomatoes[ny][nx] == 0:
                    q.append((ny, nx))
                    tomatoes[ny][nx] = tomatoes[y][x] + 1
                    visited[ny][nx] = True


def check_tomatoes():
    max_day = 0
    for row in range(N):
        for col in range(M):
            if tomatoes[row][col] == 0:
                return -1
            else:
                if tomatoes[row][col] - 1 > max_day:
                    max_day = tomatoes[row][col] - 1
    return max_day


for row in range(N):
    for col in range(M):
        if tomatoes[row][col] == 1 and visited[row][col] == False:
            start_nodes.append((row, col))
BFS(start_nodes)

print(check_tomatoes())

말이 쉽지, 체감상 지금까지 풀어본 BFS 문제중에 가장 어려웠던 축인 것 같네요. (거의 한시간 넘게 걸렸네요 -__-;)

코드가 어려웠다기보단 BFS의 분기 수(최소 경로) 찾기 + 시작점 둘일때 케이스 처리하기를 이중으로 맞으니 정말 막막했던 문제입니다.

그래도, 덕분에 실버 3으로 승급했습니다!! 😆