백준 7576 | BFS | 토마토 [파이썬 python]

7576번: 토마토

 

코드

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

m, n = map(int, input().split()) # 가로, 세로
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

# 익은 토마토의 위치 queue에 추가
queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

# BFS 함수 정의
def bfs():
    while queue:
        x, y = queue.popleft()
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 상하좌우에 익지 않은 토마토(0)가 있으면 1을 더해 몇 번째인지 세주고
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny)) # 큐에 새로운 토마토 위치 추가

# BFS; 토마토 익히기 시작
bfs()

# bfs 종료 후
day = 0
for row in graph:
    for i in row:
        if i == 0:  # 익지 않은 토마토가 있으면(=토마토가 모두 익지 못하는 상황) -1 출력
            print(-1)
            exit() # 다음 행의 여부와 관계 없이 -1만 출력해야하므로 종료시킴
    else: # 그래프에서 가장 큰 값이 마지막으로 익은 토마토임 → 한 줄씩 최댓값을 day로 갱신하며 최댓값 찾기
        day = max(day, max(row)) 

# 처음 시작을 0이 아닌 1부터 했으므로 -1을 해야 날짜를 구할 수 있음 
print(day-1)

 

가장 먼저 M, N 그리고 토마토의 정보를 입력받아 graph에 추가한다.

m, n = map(int, input().split()) # 가로, 세로
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

문제에서 토마토가 모두 익는 최소 날짜를 구하라고 했으므로 BFS를 사용해야 하는 문제이다. 처음에는 DFS로 접근했다가 답이 출력 안 되는 상황을 맞닥뜨렸었다.

따라서 BFS에 필요한 queue에 익은 토마토의 위치(=1)를 모두 찾아 추가한다.

# 익은 토마토의 위치 queue에 추가
queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

그다음으로 BFS를 실행하기 위해 BFS 함수 정의를 해준다.

# BFS 함수 정의
def bfs():
    while queue:
        x, y = queue.popleft() # 익은 토마토(=1) 좌표를 하나씩 가져옴
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 상하좌우에 익지 않은 토마토(0)가 있으면 1을 더해 몇 번째인지 세주고
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))  # 큐에 새로운 토마토 위치 추가

queue에 있는 좌표를 하나씩 가져와 상하좌우 4방향으로 이동하며 이동한 위치가 익지 않은 토마토(=0)인지 확인한다.

주변 값들 중 0인 좌표가 있으면 해당 값을 graph[x][y]+1로 바꿔준다..

가장 첫 번째 x, y 좌표에 대한 graph[x][y]는 1일 것이므로, 그 주변의 graph[nx][ny]=0이면 1+1=2로 바꿔주는 것이다.

이렇게 계속해서 이전 좌표의 graph 값에 +1씩 해주면 몇 번째날 해당 토마토가 익었는지 확인할 수 있다.

graph[x][y] 주변인 graph[nx][ny] 위치의 토마토는 익었으므로 queue에 해당 좌표를 추가해 그 위치에서도 bfs를 진행할 수 있도록 한다.

 

BFS 함수를 실행하고, 마지막으로 모든 토마토가 익는 최소 일수를 구한다.

# BFS; 토마토 익히기 시작
bfs()

# bfs 종료 후
day = 0
for row in graph:
    for i in row:
        if i == 0:  # 익지 않은 토마토가 있으면(=토마토가 모두 익지 못하는 상황) -1 출력
            print(-1)
            exit() # 다음 행의 여부와 관계 없이 -1만 출력해야하므로 종료시킴
    else: # 그래프에서 가장 큰 값이 마지막으로 익은 토마토임 → 한 줄씩 최댓값을 day로 갱신하며 최댓값 찾기
        day = max(day, max(row))

# 처음 시작을 0이 아닌 1부터 했으므로 -1을 해야 날짜를 구할 수 있음 
print(day-1)

BFS가 끝난 graph의 행을 하나씩 불러 값을 확인한다.

만약 행 안에 0인 값이 존재하면 익지 않은 토마토가 있는 것이므로 -1을 출력하도록 하고 종료(exit)한다.

-1을 출력한 뒤 exit() 함수를 사용하지 않으면 다음 좌표를 또 확인하게 되어 오류가 발생한다.

행에 0인 값이 없으면 해당 행에는 모두 익은 토마토가 있는 것이므로 해당 행에서 가장 큰 값을 day로 바꾼다.

graph에 존재하는 모든 토마토 중 가장 마지막에 익은 날짜를 찾아야 한다. 그러므로 한 행에서 최댓값들을 찾아 계속해서 큰 값으로 갱신해 주면 최종 날짜를 구할 수 있다.

만약, 기존 day값이 크면 그대로 유지할 수 있도록 max(day, max(row))로 작성하여 두 값 중 큰 값으로 선택하도록 하였다.

 

모든 행을 확인했으면 마지막으로 day를 출력한다.

이때 토마토에 1부터 +1씩 해주었기 때문에 구하고자 하는 최소 일수는 day-1을 해주어야 한다.