7569

날짜 : 2022. 12. 04

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

m, n, h = map(int, sys.stdin.readline().split())  # 가로, 세로, 높이
box = list()
visited = [[[False] * m for _ in range(n)] for _ in range(h)]
q = deque()
for i in range(h):
    floor = list()
    for j in range(n):
        floor.append(list(map(int, sys.stdin.readline().split())))
    box.append(floor)


def bfs():  # 높이, 행, 열
    # 위, 아래, 우, 좌, 앞, 뒤
    dz = [1, -1, 0, 0, 0, 0]  # 높이
    dx = [0, 0, 1, -1, 0, 0]  # 행
    dy = [0, 0, 0, 0, 1, -1]  # 열
    while q:
        temp = q.popleft()
        for i in range(6):
            z = temp[0] + dz[i]
            x = temp[1] + dx[i]
            y = temp[2] + dy[i]
            if z in range(h) and x in range(n) and y in range(m):  # 범위에 있는 경우
                if box[z][x][y] == 0 and not visited[z][x][y]:  # 아직 안익은 토마토, 방문 x상태
                    box[z][x][y] = box[temp[0]][temp[1]][temp[2]] + 1  # 익음처리
                    q.append([z, x, y])

    return


for i in range(h):  # 높이
    for j in range(n):  # 행
        for k in range(m):  # 열
            if box[i][j][k] == 1 and not visited[i][j][k]:  # 익은 토마토인 경우
                #print(i, j, k)
                q.append([i, j, k])  # 마킹(for문으로 돌리는 경우 중복현상 발생)
                visited[i][j][k] = True
bfs()
res = 0
for i in range(h):
    for j in range(n):
        for k in range(m):
            res = max(box[i][j][k], res)
            if box[i][j][k] == 0:  # 안익은 토마토가 있는 경우
                print(-1)  # -1 출력 후 프로그램 종료
                exit()
print(res-1)
#print(box)

 

 

풀이

- 2차원 배열을 활용한 BFS 문제와 비슷한 유형이다.

- 반례의 경우

10 1 1

1 0 0 0 0 0 0 0 0 1

위처럼 나온다면 양끝에서 동시에 익기 시작해 결국 1 2 3 4 5 5 4 3 2 1 의 형태가 나와야 한다.

- 그렇지만 단순히 for 문을 돌리면서 BFS를 실행했을 때는 1 2 3 4 5 6 7 8 9 1 이 나오기 때문에 첫 for문을 통한 탐색에서는 방문하지 않았고 익은(값이 1) 토마토의 좌표만을 deque에 넣은 다음 이를 활용해서 BFS를 돌려야 한다.

- 그렇다면 위의 경우는 자연스럽게 맨 앞의 케이스를 한번 탐색하고 뒤의 케이스를 탐색한다.

- 그리고 마지막에는 기존 일수보다 1이 크기 때문에 그 값만 차감하여 출력한다.

 

알게된 점

- 토마토가 이미 익은 경우 더 빨리 익을 수 있을 때 이를 최신화하는 방식을 떠올리지 못했다.

- 기존문제에서의 풀이는 전부 맞았지만 질문글에서 찾은 위의 반례에서 계속 걸렸다.

- 그래서 풀이를 찾아보았고 위의 풀이를 알게 되었다.

- 지난번에도 DFS였나 BFS였나 문제에서 똑같이 틀린것 같은데 다음에는 똑같이 틀리지 않도록 이 문제는 꼭 기억해야겠다.

 

 

 

참고 사이트

- for문에서의 마킹 : https://velog.io/@falling_star3/백준Python-7569번-토마토

[백준][Python] 7569번 토마토

- 3차원 배열 : https://dojang.io/mod/page/view.php?id=2297 

파이썬 코딩 도장: 23.6 연습문제: 3차원 리스트 만들기