[항해99] 99클럽 코테 스터디 12일차 TIL + (BFS 백준 7569)

99클럽 코테 스터디 12일차 TIL + BFS 백준 7569

오늘의 학습 키워드

• BFS
• 백준 7569
• 토마토
• 3차원 배열 구현

공부한 내용

1. 3차원 배열 구현

• 3중 리스트 컴프리핸션
• graph[높이][세로][가로]

# 3차원 배열 초기화
graph = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]

# 값 입력 받기
for i in range(H):
    for j in range(N):
        graph[i][j] = list(map(int, input().split()))

2. BFS 구현

• 방향 벡터 설정

# 6방향 이동 (위, 아래, 앞, 뒤, 왼쪽, 오른쪽)
dx = [0, 0, 0, 0, -1, 1]
dy = [0, 0, -1, 1, 0, 0]
dz = [-1, 1, 0, 0, 0, 0]

• 큐 초기화(익은 토마토 위에서 시작해야함)

  queue = deque()
  for i in range(H):
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 1:
                queue.append((i, j, k))

• 좌표 이동 및 범위 체크

범위를 벗어나지 않는지 체크
익지 않은 토마토(0)인 경우만 처리
현재 위치의 값 + 1을 저장하여 날짜 계산

if 0 <= nz < H and 0 <= nx < N and 0 <= ny < M and graph[nz][nx][ny] == 0:
    graph[nz][nx][ny] = graph[z][x][y] + 1
    queue.append((nz, nx, ny))

4. 전체 코드

# 항해 Day 12
# 백준 7569
from collections import deque
import sys
input = sys.stdin.readline

M, N, H = map(int, input().split())

# 먼저 3차원 배열 초기화
graph = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]

# 값 입력 받기
for i in range(H):
    for j in range(N):
        graph[i][j] = list(map(int, input().split()))


dx = [0, 0, 0, 0, -1, 1]
dy = [0, 0, -1, 1, 0, 0]
dz = [-1, 1, 0, 0, 0, 0]

def BFS():
    queue = deque()
    # 입력이 완료된 후 익은 토마토 위치를 큐에 추가
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if graph[i][j][k] == 1:
                    queue.append((i, j, k))

    while queue:
        z, x, y = queue.popleft()
        for i in range(6):
            nz = z + dz[i]
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nz < H and 0 <= nx < N and 0 <= ny < M and graph[nz][nx][ny] == 0:
                graph[nz][nx][ny] = graph[z][x][y] + 1
                queue.append((nz, nx, ny))

# BFS 실행
BFS()

# 결과 확인
day = 0
for i in range(H):
    for j in range(N):
        for k in range(M):
            if graph[i][j][k] == 0:  # 익지 않은 토마토가 있다면
                print(-1)
                exit()
            day = max(day, graph[i][j][k])

# 처음 토마토가 1이었으므로 실제 일수는 최댓값 - 1
print(day - 1)

오늘의 회고

• 3차원 배열이라는 것부터 쉽지 않았다. [높이][세로][가로]인 것도 헷갈려서 애를 먹었다.
• 초기 큐를 설정할 때 시작 점이 익은 토마토 지점이라는 것을 고려해야 하는 것
• 마지막 출력 과정에서 exit() 대신에 break를 사용해서 틀렸었다. 익지 않은 토마토가 발견되면 더 이상의 계산이 무의미하기 때문에 exit()을 통해서 -1을 출력하고 프로그램을 종료해야 한다. break를 사용할 경우 반복문만 종료되어 이후 day 계산이 실행되어 틀려버림