백준 6593번 상범 빌딩

문제

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

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

문제풀이

사용한 알고리즘 : BFS

(1) 코드 10~11

 string 2차 배열로 건물정보를 받았습니다.
 ' arr[x][y][z] : z층, x행, y열 ' 로 설정하였습니다.

(2) 코드 7~8

 이동 방향 6 개에 대한 배열입니다.
 순서대로 ' 위row, 아래row, 왼쪽column, 오른쪽column, 위층, 아래층' 이동입니다.

(3) 코드 14~40

 BFS 를 구현하는 함수입니다.
 queue에는 tuple<층, row, column, 걸린시간 > 이 들어갑니다.
 매 탐색시, 코드 (2)의 6가지 방향 중 이동 가능한 곳을 찾습니다.