[Lv.2] 미로 탈출 - JavaScript

문제

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

 

 

풀이

시작점에서 레버까지, 레버에서 도착점까지의 최단 거리의 합을 구한다

최단거리라 BFS 사용함

왜 이렇게 시간초과가 날까 했는데 내가 visited를 아주 비효율적으로 생성하고 있었다

어디서 본 건지는 모르겠지만,,  절대 이렇게 하면 안되고,,

let visited = new Array(row)
    for(let i = 0; i< row;i++) {
        visited = new Array(col).fill(false)
    }

이렇게 하면 된다. 맵 짱!

let visited = Array(row)
      .fill()
      .map(() => Array(col).fill(false));

 

 

코드

function solution(maps) {
  let answer = 0;
  const row = maps.length;
  const col = maps[0].length;

  const di = [0, 0, 1, -1];
  const dj = [1, -1, 0, 0];

  // 너비우선 탐색
  const BFS = (i, j, goal) => {
    // 시작점에서 레버, 레버에서 도착점 각각 구해야 하므로 visited는 각각의 BFS가 실행될 때 초기화 되어야 함
    let visited = Array(row)
      .fill()
      .map(() => Array(col).fill(false));

    let queue = [];
    // 시작점의 방문 처리, 그리고 큐에 넣어주기
    visited[i][j] = true;
    // [행 번호, 열 번호, 지금까지의 누적 거리]
    queue.push([i, j, 0]);

    while (queue.length > 0) {
      const [ii, jj, cnt] = queue.shift();
      // 탈출조건
      if (maps[ii][jj] === goal) {
        // BFS이므로 가장 처음 값이 최단 거리
        return cnt;
      }

      // 4방향 모두 탐색
      for (let i = 0; i < 4; i++) {
        const ni = ii + di[i];
        const nj = jj + dj[i];
        if (
          ni >= 0 &&
          ni < row &&
          nj >= 0 &&
          nj < col && // 새로운 인덱스가 맵의 범위를 넘지 않으면서
          maps[ni][nj] !== "X" && // 벽이 아닌 경우
          !visited[ni][nj] // 방문한 적이 없는 경우
        ) {
          visited[ni][nj] = true; // 방문처리 해주기
          queue.push([ni, nj, cnt + 1]); // 새로운 인덱스와 거리를 큐에 삽입
        }
      }
    }
  };

  // 시작지점을 찾아서 너비우선탐색
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      // S to L
      if (maps[i][j] === "S") {
        answer += BFS(i, j, "L");
      }
      // L to E
      else if (maps[i][j] === "L") {
        answer += BFS(i, j, "E");
      } else continue;
    }
  }

  return answer ? answer : -1;
}