미로 탈출

작성일 : 2024.11.09

1. 문제 파악

문제의 요점 : 너비우선탐색 BFS방식을 통해 최단거리를 구하는 방식

2. 내 풀이

function findDistance(maps, start, target) {
  var moveCount = 0;
  let moveX = [1, -1, 0, 0];
  let moveY = [0, 0, 1, -1];

  var goX = 0;
  var goY = 0;

  maps[start[0]][start[1]] = "X";

  var queue = [start];

  while (queue.length > 0) {
    var size = queue.length;
    for (var i = 0; i < size; i++) {
      let [x, y] = queue.shift();
      for (var k = 0; k < 4; k++) {
        goX = x + moveX[k];
        goY = y + moveY[k];
        if (
          goX >= 0 &&
          goX < maps.length &&
          goY >= 0 &&
          goY < maps[0].length &&
          maps[goX][goY] !== "X"
        ) {
          if (maps[goX][goY] === target) {
            return moveCount + 1;
          } else {
            queue.push([goX, goY]);
            maps[goX][goY] = "X";
          }
        } else {
          continue;
        }
      }
    }
    moveCount++;
  }

  return -1;
}

function solution(maps) {
  var answer = 0;
  var findLever = -1;
  var findExit = -1;

  var start = [];
  var lever = [];

  // Find Start Point, Lever Point (Starting Point)
  for (let i = 0; i < maps.length; i++) {
    for (let k = 0; k < maps[i].length; k++) {
      if (maps[i][k] === "S") {
        start = [i, k];
      } else if (maps[i][k] === "L") {
        lever = [i, k];
      }
    }
  }

  let mapsLever = maps.map((item) => item.split(""));
  let mapsExit = maps.map((item) => item.split(""));
  findLever = findDistance(mapsLever, start, "L");
  findExit = findDistance(mapsExit, lever, "E");

  if (findLever !== -1 && findExit !== -1) {
    answer = findLever + findExit;
  } else {
    answer = -1;
  }

  return answer;
}

풀이 방식

우선적으로 start포인트, lever포인트를 찾아야 한다고 생각했다.
그렇게 잡은 start포인트와 lever포인트를 사용하여, start -> lever , lever -> end까지의 두번의 최단거리를 찾아, 찾은 두개의 최단거리를 더해 최종값을 반환하는 구조로 설계했다.
javascript에서 함수로 인자값을 보낼 경우, 파라미터의 값이 변경되는 문제가 발견해, mapsLever, mapsExit 두개의 map을 구성하여 진행하였다.
최단거리를 구하는 알고리즘으로 BFS를 사용하였으며, queue의 값이 모두 없어질 때까지 무한루프를 돌면서, 만약 target이 발견되어 횟수를 return 하여 탈출하거나 모두 없어졌음에도 target을 발견하지 못한 경우에는 탈출 불가능으로 간주하여 -1을 반환하는 로직으로 설계했다.

느낀 점

코딩테스트 lv2를 이번에 본격적으로 처음 접해봤는데, 확실히 자료구조의 구현 방법에 대해 공부 및 연구할 필요성을 느꼈다. 특히 이번 문제는 BFS를 사용하지 않으면 타임아웃으로 실패를 뜬 것을 확인하여, 이를 해결하고자 javascript로 BFS를 공부 및 구현하는 데에 집중을 하여 해결하였다. 이를 통해 자료구조 공부의 필요성을 느꼈고, 이를 활용하면 협업에서 성능 개선에 큰 도움을 줄 것으로 생각이 되었다.

1. 문제 파악​

2. 내 풀이​

풀이 방식​

느낀 점​

1. 문제 파악

2. 내 풀이

풀이 방식

느낀 점