[백준 문제풀기] #7576번 - 토마토 with Python

 

이 문제는 bfs를 활용하여 풀었다. 

 

 

👩🏻‍💻 코드 구현 

from collections import deque

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
day = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])


def bfs():
    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 graph[nx][ny] == 0:
                graph[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])


bfs()
for i in graph:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    day = max(day, max(i))
print(day - 1)

 

✍🏼 코드 풀이 

1. 먼저 가로칸의 수 , 세로 칸의 수를 입력받아 토마토를 담을 2차원 배열을 생성한 뒤, 입력 값에 따라 2차원 배열에 토마토의 정보를 넣어준다. 
(익지 않은 토마토는 0으로, 익은 토마토는 1로, 토마토가 없는 경우는 -1로 쓰여있다.)

2. 2차원 배열을 한차례씩 돌아가며 토마토의 정보가 1인 경우 queue에 토마토의 2차원배열 주소를 넣어주고 너비 우선 탐색(bfs)로 탐색한다. 

3. 탐색하는 자리의 상, 하, 좌, 우를 너비 우선 탐색하여 만약 방문하지 않았다면 queue에 넣어주고 토마토가 익었다는 횟수(날짜)를 나타내기 위해 +1 을 해준다. 

4. 이런식으로 queue에 들어있는 토마토들을 다 너비우선 탐색해준 뒤, 2차원배열을 다시 하나씩 보면서 만약 2차원 배열에 담긴 토마토를 익히지 못했다면 -1을 출력,  다 익혔다면 날짜의 최대값을 출력해준다. 

.