[백준6593_자바스크립트(javascript)] - 상범 빌딩

🔴 문제

상범 빌딩

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');

let front = 0;

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

const bfs = (map, start, lrc) => {
  const [l, r, c] = lrc;
  const q = [start];

  while (q.length) {
    const [x, y, z] = q.shift();

    for (let i = 0; i < 6; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      const nz = z + dz[i];

      if (nx < 0 || ny < 0 || nz < 0 || nx >= l || ny >= r || nz >= c) {
        continue;
      }

      if (map[nx][ny][nz] === 'E') {
        return map[x][y][z] + 1;
      }

      if (map[nx][ny][nz] === '.') {
        map[nx][ny][nz] = map[x][y][z] + 1;
        q.push([nx, ny, nz]);
      }
    }
  }
  return -1;
};

// 시작 위치
while (true) {
  const [l, r, c] = inputs[front++].split(' ').map(Number);

  if (l + r + c === 0) break;

  const map = [];
  for (let i = 0; i < l; i++) {
    let floor = [];
    for (let j = 0; j < r; j++) {
      floor.push(inputs[front++].split(''));
    }
    map.push(floor);
    front++;
  }

  h: for (let i = 0; i < l; i++) {
    for (let j = 0; j < r; j++) {
      for (let k = 0; k < c; k++) {
        if (map[i][j][k] === 'S') {
          map[i][j][k] = 0;
          const ans = bfs(map, [i, j, k], [l, r, c]);

          console.log(ans === -1 ? 'Trapped!' : `Escaped in ${ans} minute(s).`);

          break h;
        }
      }
    }
  }
}

🟢 풀이

⏰ 소요한 시간 : 37분

일반적인 bfs유형! 이 문제가 살짝 까다로운 이유는 여러개의 테스트케이스를 받는 것과 6개의 방향을 확인해줘야 한다는 점

시작 위치에서부터 테스트케이스를 분류해보자면 0,0,0가 입력된다면 종료해야된다.
그래서 인덱스를 증가시켜주면서 값을 입력받아준다. 입력받아온 값이 0,0,0이면 종료해주면 된다.

만약 입력받은 값이 0,0,0이 아니라면 하나의 테스트케이스므로 l,r,c에 값을 구조분해 할당해준다.
그리고 맵을 만들어준다.

 const map = [];
  for (let i = 0; i < l; i++) {
    let floor = [];
    for (let j = 0; j < r; j++) {
      floor.push(inputs[front++].split(''));
    }
    map.push(floor);
    front++;
  }

맵을 만들었으면 시작 위치를 찾아야되는데 3차원 배열이므로 3번의 중첩반복문으로 S를 찾아준다.
S를 찾으면 해당 좌표값과 맵, 범위체크에 사용할 l,r,c 값과 같이 bfs를 수행해준다.
수행한 결과값에 따라서 출력해주면 되고 반복문을 종료해 줄텐데 break만 사용한다면 가장 안쪽반복문만 빠져나가게 되므로 반복문에 label을 붙여서 종료해준다.

bfs 내부는 일반적이지만 방향만 6방향으로 고쳐주면 된다. 6방향으로 뻗어나가면서 각 좌표가 범위를 만족하는지 확인해주고, 만약 다음으로 갈 곳이 E라면 종료 위치이기 때문에 현재 위치에서 1을 더한 결과를 리턴한다. 그게 아니라면 이동가능한 위치인지 확인해주고 이동 가능하다면 최단거리 체크한 뒤 큐에 삽입한다.

🔵 Ref