BOJ 백준 6593: 상범 빌딩

Table of contents

들어가며

걸린 시간: 21분

L, R, C가 각각 최대 30이고, 너무 대놓고 BFS 문제였습니다.
3차원 매트릭스를 BFS로 순회하는 시간복잡도는 원소들이 큐에 들어갔다 나오는 개수만큼이니 최대 Order of L*R*C입니다.
그래서 시간 초과에서 안전합니다.

접근

너무 대놓고 BFS 문제여서 접근 방법은 따로 없었던 것 같습니다.
이때까지 풀어본 BFS 문제들이 기억에 났다는 거? 정도입니다.

구현

import sys
from collections import deque

input = sys.stdin.readline


def OOB(cur_k, cur_i, cur_j):
    if cur_k < 0 or cur_k >= L:
        return True
    if cur_i < 0 or cur_i >= R:
        return True
    if cur_j < 0 or cur_j >= C:
        return True

    return False


def BFS(start_pos):
    q = deque()
    q.append(start_pos)
    start_k, start_i, start_j = start_pos
    distance[start_k][start_i][start_j] = 1
    while q:
        cur_k, cur_i, cur_j = q.popleft()
        for delta_k, delta_i, delta_j in zip(DK, DI, DJ):
            next_k, next_i, next_j = cur_k + delta_k, cur_i + delta_i, cur_j + delta_j
            if OOB(next_k, next_i, next_j):
                continue
            if board[next_k][next_i][next_j] == 1:
                continue
            if distance[next_k][next_i][next_j] > 0:
                continue

            distance[next_k][next_i][next_j] = distance[cur_k][cur_i][cur_j] + 1
            q.append((next_k, next_i, next_j))


if __name__ == "__main__":
    # 동서남북상하
    DK = [1, -1, 0, 0, 0, 0]
    DI = [0, 0, 1, -1, 0, 0]
    DJ = [0, 0, 0, 0, 1, -1]

    while True:
        L, R, C = map(int, input().strip().split())
        if L == 0 and R == 0 and C == 0:
            break
        startPos = endPos = None
        distance = [[[0 for ___ in range(C)] for __ in range(R)] for _ in range(L)]
        board = [[[0 for ___ in range(C)] for __ in range(R)] for _ in range(L)]
        for k in range(L):
            for i in range(R):
                line = input().strip()
                for j in range(C):
                    if line[j] == "S":
                        board[k][i][j] = 0
                        startPos = (k, i, j)
                    elif line[j] == "E":
                        board[k][i][j] = 0
                        endPos = (k, i, j)
                    elif line[j] == ".":
                        board[k][i][j] = 0
                    elif line[j] == "#":
                        board[k][i][j] = 1

            # read blank new line
            input().strip()
        # print("board:", board)
        BFS(startPos)
        # print(distance)
        if distance[endPos[0]][endPos[1]][endPos[2]]:
            print(
                f"Escaped in {distance[endPos[0]][endPos[1]][endPos[2]] - 1} minute(s)."
            )
        else:
            print("Trapped!")

이 문제는 사실 구현에 있어서 힘이 드는 문제입니다.
마치 삼성 코테 기출을 푸는 느낌이었습니다.
그래서 이런 문제들은 자신만의 실수를 방지할 수 있게 해주는 구현 방법을 어느정도 암기해서 문제를 봤을 때 바로 쓸 수 있는 능력이 중요한 것 같습니다.
저 같은 경우는 OOB 함수 (out of bound의 줄임말입니다 ㅎㅎ)와 DK, DI, DJ 리스트를 미리 정의해놔서 어느정도 템플릿화 시켜서 풉니다.