[programmers] 미로 탈출

📝 [Lv2] 미로 탈출

👀 문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

 

🚨 제한 사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

 

💻 입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

 

✨ 풀이 설명

레버를 당겨야만 나갈 수 있기 때문에, 시작 지점부터 레버까지와 레버부터 문까지를 따로 생각하였다.

move() 함수는 start부터 end까지 가는 BFS 로직을 담고 있다. 두 경로를 구하는 로직이 같기 때문에 매개변수로 시작 지점과 종료 지점을 넘겨주어 하나의 함수에서 계산해 주었다.
start는 시작하는 지점의 좌표를 담고 있고, end는 끝나는 지점의 문자를 가리킨다. 각 좌표는 맨 먼저 maps를 완전 탐색하며 구해 POS에 담아주었다.

갔던 곳을 재방문하지 않기 위해 갔던 곳은 벽으로 만들었는데, 이를 위해 함수를 시작할 때, maps를 복사하여 다음 로직에 지장이 없도록 해주었다.
함수는 시간을 반환하도록 하여, 각각의 경로 중 하나라도 시간을 구할 수 없다면 -1을 반환해 주었고, 그렇지 않다면 두 경로 모두 구할 수 있다는 뜻이므로 시간을 더해 반환해 주었다.

 

🕵️‍♂️ 코드

function solution(maps) {

  const DIR = [[0, -1], [0, 1], [-1, 0], [1, 0]];

  const ROW = maps.length, COL = maps[0].length;

  const POS = {};

  for (let i = 0; i < ROW; i++) {

    for (let j = 0; j < COL; j++) {

      if (maps[i][j] === 'S') POS.start = [i, j];

      if (maps[i][j] === 'L') POS.lever = [i, j];

    }

  }

  const move = (start, end) => {

    const newMaps = maps.map(line => line.split(''));

    let queue = [start], time = 1;

    while (queue.length) {

      const tmp = queue.slice();

      queue = [];

      for (const [x, y] of tmp) {

        for (const [dx, dy] of DIR) {

          if (x + dx >= 0 && x + dx < ROW && y + dy >= 0 && y + dy < COL && newMaps[x + dx][y + dy] !== 'X') {

            if (newMaps[x + dx][y + dy] === end) return time;

            newMaps[x + dx][y + dy] = 'X';

            queue.push([x + dx, y + dy]);

          }

        }

      }

      time++;

    }

    return -1;

  }

  const lever = move(POS.start, 'L');

  const end = move(POS.lever, 'E');

  if (lever === -1 || end === -1) return -1;

  return lever + end;

}