파이썬(python) 백준 7576 : 토마토

 

7576번: 토마토

문제 내용

시간 제한 : 1 초

메모리 : 256 MB

 

세로 n 가로 m의 창고에 토마토가 있다.

익은 토마토는 하루 지날때마다 4방향의 안익은 토마토를 익은 토마토로 바꿈

창고의 모든 토마토 익으려면 최소 며칠 걸리는지 구하라

• 익은 토마토 : 1
• 안익은 토마토 : 0
• 토마토 없음 : -1.

 

입력

가로 m 세로 n

nxm 크기의 창고 정보 

출력

처음부터 모든 토마토가 익은 상태면 0 출력

토마토가 모두 익지 못하는 상황이면 -1 출력

토마토가 모두 익을 수 있으면 모든 토마토 익을때까지의 최소 날짜 출력

예제 입력 1

6 4

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

예제 출력 1 
8

유형

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

풀이

이 문제는 BFS 문제다.

1. 먼저 창고의 모든 익은 토마토(1)의 위치를 bfs 의 큐에 집어넣는다.

    (x위치, y위치, 일수=0)

2. bfs 수행

 

Q. 출력 조건을 어떻게 처리해야 하는가?

입력받을때 익지 않은 토마토 개수를 구해놓고

1) 익지 않은 토마토 개수 = 0 이면 출력 0

2) bfs 돌면서 익지 않은 토마토를 방문하면 개수 -1씩 하고 마지막에 0이 되는지 확인

 

Q. 모든 토마토가 익는 최소 일수는 어떻게 구하는가?

창고의 모든 익은 토마토(1)의 위치를 bfs 의 큐에 집어넣고 bfs를 돌렸기 때문에 최소 일수로 방문이 된다.

그래서 max_day 값을 매번 갱신해주면 된다.

import sys
import collections
m,n = map(int, sys.stdin.readline().split())
board = []
normal_tomato_cnt = False
max_day = 0
dx = [1,-1,0,0]
dy = [0,0,-1,1]

for i in range(n):
    r = list(map(int, sys.stdin.readline().split()))
    normal_tomato_cnt+=r.count(0)
    board.append(r)
visited = [[False]*m for _ in range(n)]
q = collections.deque()

if normal_tomato_cnt == 0:
    print(0)
else:
    for i in range(n):
        for j in range(m):
            if board[i][j] == 1:
                q.append((i,j,0))
                visited[i][j] = True
    while q:
        cur = q.popleft()
        for i in range(4):
            xx = dx[i]+cur[0]
            yy = dy[i]+cur[1]
            max_day = max(max_day, cur[2])
            if xx >=0 and yy>=0 and xx<n and yy<m:
                next_day = cur[2]+1
                if not visited[xx][yy] and board[xx][yy] == 0:
                    normal_tomato_cnt -= 1
                    visited[xx][yy] = next_day
                    q.append((xx,yy,next_day))
    if normal_tomato_cnt != 0:
        print(-1)
    else:
        print(max_day)