[프로그래머스-level2] 게임 맵 최단거리 - javascript

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

프로그래머스

 

 

[풀이]

 

최단거리를 구하는 거니 BFS 알고리즘을 사용해야 한다.

 

알고리즘 이해만 있다면 수월하게 풀 수 있는 난이도 문제.

 

 

 

function solution(maps) {
  let answer = 1;
  let visited = maps //탐색을 마친 노드들
  let needVisit = []; //탐색해야할 노드들
  const n = maps.length; //세로
  const m = maps[0].length; //가로

  //4방향  
  const dy = [0, 1, 0, -1];
  const dx = [1, 0, -1, 0];

  needVisit.push([0, 0]); //시작점
  visited[0][0] = 0; //방문한 곳은 0으로

  
  while(needVisit.length !== 0) {// 탐색해야할 노드가 남아있다면
    let size = needVisit.length;
    
    for(let i = 0; i < size; i++) {
        let [x, y] = needVisit.shift(); // 가장 오래 남아있던 정점을 뽑아냄.
        
        for(let j = 0; j < 4; j++) {
            let nx = x + dx[j];
            let ny = y + dy[j];
            
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] === 1) {
                if(nx == n - 1 && ny == m - 1) {
                    return ++answer;
                }
                needVisit.push([nx, ny]);
                visited[nx][ny] = 0;
            }
        }
    }
    answer++;
}

return -1;
}




const testCases = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	//answer: 11
console.log(solution(testCases));

 

** for 문에 needVisit.length 를 size 로 미리 선언해서 for문에 반복횟수로 넣어줘야한다, 그렇지 않으면 needVisit의 배열의 길이가 계속 바뀌기 때문에 -> shift() 연산자로 인해 , 정답이 바뀌게 되어버릴 수 있다.