[BFS] 백준 6593. 상범빌딩 (feat. 3차원 배열)

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

 

---

문제 요약

3차원 빌딩 공간에서 출발-목적지까지 걸리는 시간 구하기

 

* 주의할 점

그동안 2차원 배열이었는데, 이건 3차원 배열. 3차원 좌표 그리면서 이해할 수 있었음.

3차원 빈배열 만드는 거랑 graph입력값 받아서 3차원으로 만드는 게 시간이 많이 들었다.

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

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

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

세로로 봤을 때 (x, y, z) 좌표에 값이 하나씩 할당 될 예정, 총 6개로 move

for i in range(6):
            ax = x+dx[i]
            ay = y+dy[i]
            az = z+dz[i]

 

답코드

import sys
from collections import deque
sys.stdin = open('./BFS/input2.txt','rt')


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

# BFS는 재귀가 필요없구나...
# 함수 안에 재귀 대신 q 반복문으로 푸는구나...
# BFS 호출은 한번만 하면 되는 것..!
def BFS(x,y,z, time):
    global l
    global r
    global c
    q = deque()
    q.append((x,y,z))
    time[x][y][z] = 1
    while q:
        x, y, z = q.popleft()
        for i in range(6):
            ax = x+dx[i]
            ay = y+dy[i]
            az = z+dz[i]
            if 0<=ax<l and 0<=ay<r and 0<=az<c :
                if g[ax][ay][az] == 'E':
                    time[ax][ay][az] = time[x][y][z]
                    print("Escaped in {0} minute(s).".format(time[x][y][z]))
                    return
        
                if time[ax][ay][az]==0 and g[ax][ay][az] == '.':
                    time[ax][ay][az] = time[x][y][z] + 1
                    # print(time[ax][ay][az], ax,ay,az)
                    q.append((ax,ay,az))
               

    
    print('Trapped!')
# l 층수
# r 행
# c 열
while True:
    l,r,c = map(int, input().split())
    if l == 0 and r == 0 and c==0:
        break
    time = [[[0]*c for _ in range(r)] for _ in range(l)]

    # 한줄 표현
    # g = [[list(map(str, input())) for _ in range(r)] for __ in range(l)]
    g = []
    for il in range(l):
        gg = [list(map(str, input().strip())) for _ in range(r)]
        input() # blanc
        g.append(gg)

    for aa in range(l):
        for bb in range(r):
            for cc in range(c):
                # print(aa,bb,cc)
                if g[aa][bb][cc] == 'S':
                    x = aa
                    y = bb
                    z = cc
                if g[aa][bb][cc] == 'E':
                    ox = aa
                    oy = bb
                    oz = cc

    #S시작지점
    #E탈출지점

    BFS(x, y, z, time)

 

추가

처음에 그래프를 한 줄로 그렸었다.

3차원 배열 그리기 g = [[list(map(str, input())) for _ in range(r)] for __ in range(l)]

 

근데, 입력라인 중간에 빈 줄로 구분이 되어서 의도치 않은 빈리스트가 자꾸 들어가가지구 index에러를 초래해서 결국 for로 받음