[백준 7576] 파이썬 - 토마토

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

7576번: 토마토

# 조건

- 토마토를 보관하는 창고가 있는데 익힌 토마토는 1, 비어있는 경우 -1, 그냥 토마토는 0으로 표시
- 익힌 토마토의 좌우상하 토마토는 다음날 익어있다.
- 이 때, 모든 토마토를 다 익히는 경우, 최소 일 수를 구하여라
- 만약, 익히지 못한다면 -1 출력

 

 

# 접근 방법

- 좌우상하 탐색이 필요하므로 델타 함수를 이용하여 접근해준다.
- 또한 바로 내 주변에 토마토가 존재하는지 알아야하므로 bfs를 통하여 queue구조를 이용해준다.

- 익힌 토마토가 있는 경우 날짜를 구해주기 위하여 +1 씩해준다.

- 마지막에 리스트의 최댓값 구해주면 된다.

 

import sys  
from collections import deque  
sys.stdin = open('input.txt')  
  
  
# 좌우상하 토마토 익힌다  
  
def bfs(good):  
	# 익힌 토마토 큐가 빌때까지 반복
    while good:  
  
        sti, stj = good.popleft()  
  
        for i, j in [[1,0], [-1,0], [0,1], [0,-1]]:  
            ni, nj = sti + i, stj + j  
            if 0 <= ni < N and 0 <= nj < M and tomato[ni][nj] == 0:  
                # 익히고 1을 더해주면서 횟수를 세어주기  
                # 여기서 나온 제일 큰 값이 정답이 될 것임
                tomato[ni][nj] = tomato[sti][stj] + 1  
                good.append([ni, nj])  
  
  
M, N = map(int, input().split())  
  
tomato = [list(map(int, input().split())) for _ in range(N)]  
# deque로 받아준다. 시간효율 up  
good = deque([])  
res = 0  
for i in range(N):  
    for j in range(M):  
        if tomato[i][j] == 1:  
            good.append([i,j])  
  
bfs(good)  
for i in tomato:  
    for j in i:  
        # 다 찾아봤는데 토마토를 익히지 못했다면 -1 출력  
        if j == 0:  
            print(-1)  
            exit(0)  
    # 다 익혔다면 최댓값이 정답  
    res = max(res, max(i))  
# 처음 시작날짜를 1로 표현했으니 1을 빼준다.  
print(res - 1)

 

• Brute Force 주제를 다루면서 델타 탐색에 대한 것을 어느정도 익혀놔서 난이도 대비 많이 어렵진 않았다.
• 문제의 조건만 잘 읽는다면 Queue를 이용한 BFS를 떠올릴 정도가 되었다고 생각하지만, 조금만 꼬아서 나와도 어려울 것 같다.
• 코딩 테스트에 있어서 BFS와 DFS는 단골이기 때문에 꼭 익혀두고 응용하는 것에 익숙해지는 것이 좋을 것 같다.