[JS] 2Level / 깊이/너비 우선 탐색(DFS/BFS) / 게임 맵 최단거리

문제 풀이 방법

• 최단 거리를 구하는 문제는 BFS를 이용해 풀어야 한다.
• 문제는 정석적인 BFS문제이며 큐를 이용해 탐색할 노드를 저장한 뒤 해단 노드의 정보를 이용해
  맵의 4방향을 검증하며 방문하지 않고, 길이 있다면 move를 1더한 값과 함께 큐에 저장한다.
• 위의 검증을 반복하며 목표 좌표에 도달할 시에 move를 반환한다.

코드 

function solution(maps) {
    let xLen = maps[0].length;
    let yLen = maps.length;
    let xGoal = xLen - 1;
    let yGoal = yLen - 1;
    let rotaX = [0, 0, -1, 1];
    let rotaY = [-1, 1, 0, 0];
    
    let que = [[0, 0, 1]];
    
    while(que.length){
        const [curX, curY, move] = que.shift();
        if(curX === xGoal && curY === yGoal) {
            return move;
        }
        
        for(let i=0; i<4; i++){
            let nextX = curX + rotaX[i];
            let nextY = curY + rotaY[i];
            if(nextX >= 0 && nextX < xLen && nextY >= 0 && nextY < yLen && maps[nextY][nextX] === 1){
                que.push([nextX, nextY, move+1]);
                maps[nextY][nextX] = 0;
            }
        }
        
    }
    return -1
}

 

 

이 문제를 풀며 DFS와 BFS의 설계 방식에 대한 차이를 알게되었다.

DFS는 재귀함수를 이용해 방문여부를 기록하며 노드끼리의 연결관계, 백트랙킹에서 사용되며,
하나만 죽어라 팬다는 느낌의 문제들에 적용하며,

 

BFS는 방문 예정인 노드를 큐에 저장 후 꺼내어 다음 방문할 노드를 알아낸 뒤 알아낸 노드를 큐에 넣는 방식으로 설계.
최단 거리를 구하는 문제에 많이 사용된다.