[Algorithm] 상범 빌딩 (백준 - 6593)

📋 문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 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 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ###	Escaped in 11 minute(s). Trapped!

✏️ 풀이

이문제는 BFS 문제였다. 다만 조금 특이한점이 3차원이라는 점이다.

 

3차원으로 되어있어 조금 복잡하다고 생각했고 테스트케이스가 여러개로 입력되었기 때문에 이 과정이 조금 까다로웠다. 나는 L, R, C가 주어지는 것에 따라 처리했다. 처음 L, R, C가 주어지면 변수에 할당해두고 map을 구성했다. tempArr이라는 임시 배열을 선언해두고 층마다 빈 줄로 구분되어 빈 줄이 입력으로 주어지면 map이라는 배열에 넣어주고 그렇지 않으면 임시배열 tempArr에 입력값을 넣었다.

 

이렇게 돌다보면 map을 모두 구성하고 새로운 L, R, C가 주어지면 이때 BFS를 돌리고 새로 L, R, C에 값을 할당하고 map을 구성하기 시작한다. 만약 "0 0 0"이 L, R, C에 할당하지만 다음 입력문이 없기 때문에 자연스레 함수가 종료된다.

 

BFS 함수는 check배열과 queue 배열, cnt 변수를 가지고 동작한다. 최소 동작을 반환해야 하기 때문에 각 상황에서 이동할 수 있는 곳을 모두 queue에 넣고 이때의 길이를 저장하고 이만큼 반복한다. 해당 반복문이 종료되면 다음 동작 횟수에 갈 수 있는 위치가 queue에 새로이 저장된다. 3차원이기 때문에 z, x, y 세개의 변수(인덱스)로 해당 위치가 갈 수 있는지("."), 갈 수 없는지("#"), 탈출구인지("E")를 확인하고 check 배열에 따라 방문했던 위치는 제외하고 탐색한다. 

 

반환된 값은 cnt인데 만약 모든 동작을 수행했음에도 탈출구("E")에 도착하지 못하면 0을 반환하고 반환된 값이 유효한지에 따라 삼항연산자를 이용해서 다른 결과물을 출력했다. 

⌨️ 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './testcase/6593.txt';

let inputs = fs.readFileSync(filePath).toString().trim().split('\n');

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

const bfs = (board, L, R, C) => {
  const check = [...new Array(L)].map(_ => [...new Array(R)].map(_ => new Array(C).fill(0)));
  let start;
  outer: for (let i = 0; i < L; i++) {
    for (let j = 0; j < R; j++) {
      for (let k = 0; k < C; k++) {
        if (board[i][j][k] === 'S') {
          start = [i, j, k];
          break outer;
        }
      }
    }
  }
  const queue = [start];
  let cnt = 0;
  check[start[0]][start[1]][start[2]] = 1;

  while (queue.length) {
    const len = queue.length;
    for (let i = 0; i < len; i++) {
      const [z, x, y] = queue.shift();
      for (let k = 0; k < 6; k++) {
        const zz = z + dz[k];
        const xx = x + dx[k];
        const yy = y + dy[k];

        if (zz < 0 || zz >= L || xx < 0 || xx >= R || yy < 0 || yy >= C) continue;
        if (board[zz][xx][yy] === '#') continue;
        if (check[zz][xx][yy]) continue;
        if (board[zz][xx][yy] === 'E') return cnt + 1;

        check[zz][xx][yy] = 1;
        queue.push([zz, xx, yy]);
      }
    }
    cnt += 1;
  }
  return 0;
};

let map = [];
let tempArr = [];
let L, R, C;
for (const input of inputs) {
  const temp = input.split(' ').map(Number);
  if (temp.length >= 3) {
    if (map.length) {
      const res = bfs(map, L, R, C);
      console.log(res ? `Escaped in ${res} minute(s).` : 'Trapped!');
    }
    [L, R, C] = temp;
    map = [];
  } else {
    if (!input) {
      map.push([...tempArr]);
      tempArr = [];
    } else {
      tempArr.push(input);
    }
  }
}