백준 7569 파이썬

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

7569번: 토마토

 

 

정답 코드

from collections import deque
from itertools import chain
from sys import stdin


M, N, H = map(int, stdin.readline().split())
board = []
queue = deque()

for h in range(H):
    temp = []
    for n in range(N):
        temp.append(list(map(int, stdin.readline().split())))
        for m in range(M):
            if temp[n][m] == 1:
                queue.append((h, n, m))
    board.append(temp)


dh = [0, 0, 0, 0, 1, -1]
dc = [0, 0, 1, -1, 0, 0]
dr = [1, -1, 0, 0, 0, 0]
while queue:
    h, r, c = queue.popleft()
    for i in range(6):
        nh = h + dh[i]
        nr = r + dr[i]
        nc = c + dc[i]
        if nh < 0 or nh >= H or nc < 0 or nc >= M or nr < 0 or nr >= N:
            continue
        if board[nh][nr][nc] == 0:
            queue.append((nh, nr, nc))
            board[nh][nr][nc] = board[h][r][c] + 1
            
answer = 1
for b in board:
    for c in chain(b):
        if 0 in c:
            print(-1)
            exit()
        else:
            answer = max(max(c), answer)

print(answer - 1)

 

접근

우선 구하고자 하는 것은 칸의 모든 토마토가 익을 때까지의 최소 날짜 다.

그 중 익지 못하는 칸이 있다면 -1 을 리턴하면 된다. 그래서  처음엔 0인 칸을 차례대로 1로 만들려고 했다.

여기서 문제점은 어떤 칸이, 몇일 째에 1이 됐는지 판별 할수 없다는 점이다. 

그럼 어떻게 해야할까? 인접한 칸(0인 지점)을 1로 바꾸는 대신, 인접 원소의 값에 +1을 하여 값을 부여하면 된다.

 

특이점

이 문제는 3차원을 다룬다. (3차 배열) 그렇기 때문에 -1을 출력해야 하는 상황을 검증하려면 for 문을 3번 돌려야하는데, 개인적으로 반복문을 3번이나 사용하는건 깔끔하지 않다고 생각하여 itertools 라이브러리의 chain() 메서드를 사용했다. chain() 메서드를 사용하면 2차 배열 구조를 1차 배열로 flatten 시킬 수 있기 때문에, 이중 for 문으로도 충분히 검증이 가능해진다.