(python) 백준 7576 - 토마토 (bfs 풀이)

백준 7576

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

7576번: 토마토

 

1. 문제 설명

 

한 단계마다 인접한 토마토가 익는 방식으로 토마토 전체가 다 익는 데 걸리는 시간을 구하는 문제

 

2. 문제 풀이

 

먼저 리스트에 토마토에 관한 정보를 입력받아 저장한다.

 

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

 

box를 돌면서 사과가 있는 위치에 대한 인덱스를 deque에 저장한다.

 

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

 

deque에 저장된 값을 시작으로 bfs알고리즘으로 인접해 있는 토마토를 탐색한다.

 

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
	#queue가 빌 때까지
    while queue:	
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #인덱스 범위 검사
            if 0 <= nx < n and 0 <= ny < m and box[nx][ny] == 0:
                #갱신된 횟수 업데이트
                box[nx][ny] = box[x][y] + 1
                #다음 좌표 queue에 추가
                queue.append([nx, ny])

 

업데이트된 box 리스트에 대하여 모든 사과가 익었는지 검사하고 익었다면 최종 횟수를 구한다.

 

#최종횟수 저장할 변수
cnt = 0
for rowList in box:
    for v in rowList:
        if v == 0:
            print(-1)
            exit()
    #각 줄 별로 최대값만 참고
    cnt = max(cnt, max(rowList))
#시작넘버가 1이므로 1을 빼준다.
print(cnt - 1)

 

3. 전체 코드

 

from collections import deque

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                queue.append([nx, ny])

m, n = map(int, input().split())
box = []
for i in range(n):
    box.append(list(map(int, input().split())))

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
bfs()

cnt = 0
for rowList in box:
    for v in rowList:
        if v == 0:
            print(-1)
            exit()
    cnt = max(cnt, max(rowList))
print(cnt - 1)