[Algorithm] 프로그래머스-미로탈출

프로그래머스 - 미로탈출

문제 파악

• 미로 탈출
  • 벽(x), 통로(이동 O)
• 루트 : 출발 지점 -> … -> 레버가 있는 칸으로 이동 -> 레버 열기 -> 미로 빠져나가는 문까지 이동
  • 레버를 당기지 않으면 출구가 있는 칸을 지나갈 수 있음

📌 백준 10026번 문제 링크

접근 방법

1. S, L, E를 시작 지점 변수에 저장
2. 통로(1)와 벽(0) 구분
3. S -> L까지 최단거리 구하기 -> BFS
4. L에서 E까지 최단거리 구하기 -> BFS
5. 3의 최단거리와 4의 최단거리 합하기
   • 둘 중 하나라도 거리가 0이면 탈출 할 수 없기 때문에 -1 반환

코드

function solution(maps) {
  let answer = 0;
  const start = [],
    lever = [],
    exit = [];
  const maze = maps.map((map) => map.split(""));

  // 통로(1)와 벽(0) 구분
  for (let i = 0; i < maps.length; i++) {
    for (let j = 0; j < maps[i].length; j++) {
      if (maze[i][j] === "X") {
        maze[i][j] = 0;
        continue;
      }
      // S, L, E를 변수에 저장
      if (maze[i][j] == "S") start.push(i, j);
      else if (maze[i][j] == "L") lever.push(i, j);
      else if (maze[i][j] == "E") exit.push(i, j);
      maze[i][j] = 1;
    }
  }

  const leverDist = bfs(start, lever, maze); // S -> L까지 최단거리 구하기 -> BFS
  const exitDist = bfs(lever, exit, maze); // L에서 E까지 최단거리 구하기 -> BFS
    // 3의 최단거리와 4의 최단거리 합하기
  return !leverDist || !exitDist ? -1 : leverDist + exitDist;
}
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];

const bfs = (start, end, map) => {
  const dist = Array.from(Array(map.length), () =>
    Array(map[0].length).fill(0),
  );

  const [startX, startY] = start;
  const queue = [[startX, startY]];

  while (queue.length > 0) {
    const [x, y] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [x + dx[i], y + dy[i]];
      if (nx < 0 || nx >= map.length || ny < 0 || ny >= map[0].length) continue;
      if (dist[nx][ny] !== 0 || map[nx][ny] == 0) continue;

      dist[nx][ny] = dist[x][y] + 1;
      queue.push([nx, ny]);
    }
  }
  return dist[end[0]][end[1]];
};

---

지난주에 포트폴리오 하느라 알고리즘을 못해서 오랜만에 문제 풀었는데 BFS 문제였다 !
기억을 더듬더듬더듬해서 풀어봤는데 다행히 정답이 떴다ㅎㅎ
아직도 BFS 문제를 풀면 너무 신난다… BFS/DFS는 내 평생 숙제였는데 !! 이제 DFS로 넘어가야겠다

---

END