[Algorithm] 최단거리 알고리즘 문제 Node.js

문제

 

세로/가로 길이가 각각 M,N인 room의 지도가 2차원 배열로 주어집니다. room의 지도 중 1은 장애물이고, 0은 이동 가능한 경로를 의미합니다. 로봇은 지도 위를 1분에 한칸씩 이동할 수 있게 됩니다. 로봇의 현재 위치와 목표 지점이 주어질 경우 이동하는데 최소시간을 반환해야 합니다.

 

 

입/출력

 

입력 1 room

• 배열을 요소로 가지는 배열입니다.
• room.length = M
• room[i]는 Number 타입
• room[i].length = N
• room[i][j]는 세로 i, 가로 j인 지점의 좌표입니다.
• room[i][j]는 0 또는 1입니다.

입력 2 : src

• Number 타입 배열
• src.length = 2
• src[i] >= 0
• src는 차례대로 x,y 좌표를 의미합니다.

입력 3 : dst

• Number 타입 배열
• dst.length  = 2
• dst[i] >= 0
• dst는 차례대로 x,y 좌표를 의미합니다.

출력

Number 타입의 소요 시간을 반환해야 합니다.

 

 

주의사항

 

• M, N은 20 이하 자연수 입니다.
• src, dst는 항상 로봇이 지나가는 통로입니다.
• src에서 dst로 가는 경로는 항상 존재한다고 가정합니다.

 

풀이

 

로봇이 이동할 수 있는 경로는 room의 요소가 0인 지점입니다. 따라서 시작지점에서 도착지점까지 도달할 수 있는 경로는 BFS와 DFS 알고리즘을 사용해 구해낼 수 있습니다. 

DFS 풀이 

DFS는 깊이우선 탐색으로 시작지점에서 목표지점까지의 경로를 우선적으로 탐색하게 됩니다. 현재 경로에서 이동가능한 모든 경우의 수를 탐색하지 않고, 탐색 가능한 한가지 방법으로 더 이상 탐색이 불가능 할 때 까지 탐색을 진행합니다. 한번에 목표 지점 까지 도달하지 못하면 시간 복잡도는 BFS에 비해 증가합니다.

 

 

새롭게 이동한 좌표값이 room 지도 내에 위치하는지 검사하는 유효성 검사가 진행되고, 만약 이동가능한 경로이거나 이전보다 높은 단계인 경우 room에 이동 레벨을 기재합니다. 

const [row, col] = newMN;

if(row < 0 || row >= M || col < 0 || col >= N) return;

if(room[row][col] === 0 || room[row][col] > step){
    room[row][col] = step;
}else{
    return;
}

 

상하좌우 4방향으로 이동가능한 새로운 좌표를 검색합니다. 

aux(M, N, [row+1, col], step + 1);
aux(M, N, [row-1, col], step + 1);
aux(M, N, [row, col+1], step + 1);
aux(M, N, [row, col-1], step + 1);

 

도착 지점 검색이 완료 되면 최종적으로 도작지점의 갱신된 step을 출력합니다.

const [r, c] = dst;
return room[r][c] - 1;

 

DFS 알고리즘 Node.js 구현

const DFS = () => {
    const aux = (M, N, newMN, step) => {
        const [row, col] = newMN;

        if(row < 0 || row >= M || col < 0 || col >= N) return;

        if(room[row][col] === 0 || room[row][col] > step){
            room[row][col] = step;
        }else{
            return;
        }

        aux(M, N, [row+1, col], step + 1);
        aux(M, N, [row-1, col], step + 1);
        aux(M, N, [row, col+1], step + 1);
        aux(M, N, [row, col-1], step + 1);
    }

    aux(room.length, room[0].length, src, 1);
    console.log(room);

    const [r, c] = dst;
    return room[r][c] - 1;
}

 

BFS 풀이

시작지점에서 이동 가능한 경로를 모두 Queue에 담습니다. Queue에서 좌표를 1개씩 뽑아서 유효성 검사를 진행 한 후 이동가능한 경로이면서 방문하지 않은 지점을 찾아 새롭게 Queue에 담고 방문 여부를 체크합니다. room 지도내에는 이동한 레벨을 체크하면서 Queue가 모두 빌 때 까지 반복합니다.

새로운 좌표값, 방문 체크 배열, room의 전체적인 길이 등을 선언해줍니다.

const newX = [-1,1,0,0];
const newY = [0,0,-1,1];
const M=room.length;
const N=room[0].length;

// 방문지점 체크
const visit = Array(M).fill(0).map(()=>Array(N).fill(false));

 

 

유효성 검사 함수를 작성합니다.

// 유효성 검사 함수
const isValid = (m,n) =>{
    if(m < 0 || m >= M || n < 0 || n >= N){
        return false;
    }

    return true;
}

 

최초로 시작 좌표를 Queue에 추가하고 방문 여부를 체크합니다. Queue가 빌 때 까지 좌표를 이동하면서 가능한 모든 경로를 탐색합니다.

const queue = [];
queue.push(src);
visit[src[0]][src[1]] = true;

while(queue.length > 0){
    const temp = queue.shift();
    const [f, l] = temp;

    for(let i=0; i<4; i++){
        const Y = f+newY[i];
        const X = l+newX[i];

        if(isValid(Y, X)){
            if(room[Y][X] === 0 && !visit[Y][X]){
                visit[Y][X] = true;
                room[Y][X] = room[f][l] + 1;
                queue.push([Y,X])
            }
        }
    }


}

 

모든 경로 탐색이 완료되면 도착 지점의 좌표값으로 이동 레벨을 출력합니다.

const [r, c] = dst;
return room[r][c];

 

BFS 알고리즘 Node.js 구현

const BFS = () =>{
    // 상하좌우 이동
    const newX = [-1,1,0,0];
    const newY = [0,0,-1,1];
    const M=room.length;
    const N=room[0].length;

    // 방문지점 체크
    const visit = Array(M).fill(0).map(()=>Array(N).fill(false));

    // 유효성 검사 함수
    const isValid = (m,n) =>{
        if(m < 0 || m >= M || n < 0 || n >= N){
            return false;
        }

        return true;
    }

    // BFS 알고리즘
    const queue = [];
    queue.push(src);
    visit[src[0]][src[1]] = true;

    while(queue.length > 0){
        const temp = queue.shift();
        const [f, l] = temp;

        for(let i=0; i<4; i++){
            const Y = f+newY[i];
            const X = l+newX[i];

            if(isValid(Y, X)){
                if(room[Y][X] === 0 && !visit[Y][X]){
                    visit[Y][X] = true;
                    room[Y][X] = room[f][l] + 1;
                    queue.push([Y,X])
                }
            }
        }


    }
    const [r, c] = dst;
    return room[r][c];
}

 

 

 

 

 

최단거리 이동 알고리즘

 

특정 지점에서 목표지점까지 이동하는 문제는 다익스트라 알고리즘을 사용합니다. 가중치 그래프를 사용해서 이동한 거리를 계산하고 가장 최단 거리를 구할 수 있습니다. 네비게이션이나 항공권 구매 서비스를 구축할 때 사용될 수 있습니다.

다익스트라 알고리즘은 BFS와 DFS로 간단하게 구현할 수 있습니다. Weighted Graph 클래스를 작성하고, 이를 기반으로 작성할 수도 있지만 간단한 로직은 BFS와 DFS로 구현 가능합니다. 주어진 room 지도 내에서 이동가능한 조건과 최단거리 조건을 만족하면서 이동 경로를 구하기 위해서는 이동 방법, 방문여부, 가중치 계산 등 로직이 필요합니다.

 

 

 

[Algorithm] Balance Brackets in JS ( 스택(stack) 알고리즘 활용 )

 

[Blockchain] 탭 루트(Tap Root)란? 슈노르 서명?

 

[Algorithm] 두 배열에서 k 번째 수 찾기 Javascript(getItemFromTwoSortedArrays 알고리즘)

 

[Algorithm] treeBFS 알고리즘 Javascript Node.js 구현하기