프로그래머스 LEVEL 2(미로 탈출)

사용 언어 : javascript
해결 날짜 : 2023-04-24
해결 방법 :
- dfs를 활용하여 문제 해결
  - 시작 지점에서 레버까지의 최단 거리, 레버에서 끝 지점까지의 최단 거리 두 개를 구해야 하므로 dfs를 두번 수행
  - 처음에 maps를 돌며 시작 지점, 레버, 끝 지점 저장하고, 계산에 용이하도록 각 값이 0과 -1인 2차원 배열로 변환
  - 각 bfs마다 출발지와 목적지, visited를 설정하여 목적지에 도달하거나 큐가 비어 있게 될 때까지 반복하며 최단 거리 탐색

회고 :

처음에 S와 L의 최단 거리, L과 E의 최단 거리 두 개를 구해야 한다고 생각했고, bfs를 두 번 사용해서 문제를 해결하려 했다.

function solution(maps) {
  const moves = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const positions = {};
  const maxWidth = maps[0].length,
    maxHeight = maps.length;
  const visited = Array.from({ length: maxHeight }, () =>
    Array.from({ length: maxWidth }, () => false),
  );

  maps = maps.map((map, i) =>
    map.split('').map((v, j) => {
      if (v === 'S' || v === 'E' || v === 'L') {
        positions[v] = [i, j];
        return 0;
      } else if (v === 'O') {
        return 0;
      } else {
        return -1;
      }
    }),
  );

  const bfs = (from, to, visited) => {
    const q = [from];
    visited[from[0]][from[1]] = true;

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

      if (x === to[0] && y === to[1]) {
        break;
      }

      visited[x][y] = true;

      moves.forEach((move) => {
        const [nextX, nextY] = [x + move[0], y + move[1]];

        if (
          nextX < 0 ||
          nextY < 0 ||
          nextX >= maxHeight ||
          nextY >= maxWidth ||
          maps[nextX][nextY] < 0 ||
          visited[nextX][nextY]
        ) {
          return;
        }

        maps[nextX][nextY] = maps[x][y] + 1;
        q.push([nextX, nextY]);
      });
    }

    return maps[to[0]][to[1]];
  };

  const d1 = bfs(
    positions.S,
    positions.L,
    visited.map((v) => [...v]),
  );
  if (d1 === 0) {
    return -1;
  }

  const d2 = bfs(
    positions.L,
    positions.E,
    visited.map((v) => [...v]),
  );
  if (d2 === 0 || d2 === d1) {
    return -1;
  }

  return d2;
}

그러나 테스트 케이스 대부분에서 시간 초과 문제가 발생했다.
dfs가 아닌 bfs인데 방문 여부를 각 moves 바깥쪽에서 변경했기에 발생한 문제였다. 바깥쪽에서 변경한다면 똑같은 원소가 큐에 들어갈 가능성이 있으므로 시간 초과가 난 것이다.
따라서 moves 안쪽에서 방문 여부를 변경하도록 로직을 수정했더니.. 성공!!

코드

function solution(maps) {
  const moves = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const positions = {};
  const maxWidth = maps[0].length,
    maxHeight = maps.length;
  const visited = Array.from({ length: maxHeight }, () =>
    Array.from({ length: maxWidth }, () => false),
  );

  maps = maps.map((map, i) =>
    map.split('').map((v, j) => {
      if (v === 'S' || v === 'E' || v === 'L') {
        positions[v] = [i, j];
        return 0;
      } else if (v === 'O') {
        return 0;
      } else {
        return -1;
      }
    }),
  );

  const bfs = (from, to, visited) => {
    const q = [from];
    visited[from[0]][from[1]] = true;

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

      if (x === to[0] && y === to[1]) {
        break;
      }

      moves.forEach((move) => {
        const [nextX, nextY] = [x + move[0], y + move[1]];

        if (
          nextX < 0 ||
          nextY < 0 ||
          nextX >= maxHeight ||
          nextY >= maxWidth ||
          maps[nextX][nextY] < 0 ||
          visited[nextX][nextY]
        ) {
          return;
        }

        visited[nextX][nextY] = true;
        maps[nextX][nextY] = maps[x][y] + 1;
        q.push([nextX, nextY]);
      });
    }

    return maps[to[0]][to[1]];
  };

  const d1 = bfs(
    positions.S,
    positions.L,
    visited.map((v) => [...v]),
  );
  if (d1 === 0) {
    return -1;
  }

  const d2 = bfs(
    positions.L,
    positions.E,
    visited.map((v) => [...v]),
  );
  if (d2 === 0 || d2 === d1) {
    return -1;
  }

  return d2;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges