프로그래머스 Lv.2. 미로 탈출

function BFS(start, arr, target) {
  // 상하좌우
  const tranX = [-1, 1, 0, 0];
  const tranY = [0, 0, -1, 1];
  

  const queue = [start];
  let time = 0;

  while (queue.length > 0) {
    let size = queue.length;

    for (let i = 0; i < size; i++) {
      let [x, y] = queue.shift();

      // 상하좌우 이동
      for (let k = 0; k < 4; k++) {
        let nx = x + tranX[k];
        let ny = y + tranY[k];

        // 다음 위치가 유효하고 벽이 아닌 경우
        if (
          nx >= 0 &&
          ny >= 0 &&
          nx < arr.length &&
          ny < arr[0].length &&
          arr[nx][ny] !== "X"
        ) {
          // 목표지점에 도달한 경우
          if (target === arr[nx][ny]) {
            return time + 1; // 경과 시간 반환
          }

          queue.push([nx, ny]); // 다음 위치를 큐에 추가
          arr[nx][ny] = "X"; // 해당 위치를 방문했음을 표시
        }
      }
    }

    time++; // 현재 시간 증가
  }

  return -1;
}


function solution(maps) {
  let leverCord;
  let startCord;
  let maps1 = maps.map((element) => element.split("")); 
  let maps2 = maps.map((element) => element.split(""));

  // 출발 지점과 레버의 위치 찾기
  for (let x = 0; x < maps.length; x++) {
    for (let y = 0; y < maps[0].length; y++) {
      if (maps[x][y] === "L") {
        leverCord = [x, y];
      }

      if (maps[x][y] === "S") {
        startCord = [x, y];
      }
    }
  }


  let time1 = BFS(startCord, [...maps1], "L");   // 출발 지점에서 레버까지의 최소 시간
  let time2 = BFS(leverCord, [...maps2], "E");   // 레버에서 출발 지점까지의 최소 시간

  if (time1 === -1 || time2 === -1) {
    return -1;
  }

  // 출발-레버 최소 시간 + 레버-도착 최소 시간
  return time1 + time2;
}

- 최단거리를 구하는 bfs 함수를 만들기

- 시작점에서 레버까지의 최단거리 + 레버에서 도착점까지의 최단거리