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

문제링크

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

프로그래머스

간만에 올리는 코테 풀이다.. 최근에 bfs, dfs 개념을 공부하고 정리할 겸 내가 푼 풀이를 다 풀어서 기록해보려고 한다.

이번 문제는 bfs(너비우선 탐색) 방법으로 문제를 풀었다.

이렇게 캐릭터가 위치해 있으면 빨간색 오각형이 있는 위치까지 최단거리로 이동하면 된다.

검은색 부분은 막혀있는 곳이므로 지나갈 수 없고 흰색 부분을 지나되 가장 짧은 거리로 이동하면 승리한다.

 

여기서 제한사항을 잘 읽어보자.

맵은 n x m 으로 되어있는 2차 배열이다.

 

이런식으로 되어있으며 가로 즉 n이 2차원 배열의 요소가 된다. 

이제 풀이를 통해 자세히 살펴보자!! 

 

풀이

function solution(maps) {
    const HEIGHT = maps.length;
    const WIDTH = maps[0].length;
    const moves = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    let result = -1;
    
    const getIsValid = (y, x) => {
        if(x >= 0 && y >= 0 && x < WIDTH && y < HEIGHT && maps[y][x] === 1) return true;
    }
    
    const bfs = (start, end) => {
        const queue = [[start, end, 1]];
        
        while(queue.length){
            const [curY, curX, curCount] = queue.shift();
            
            if(curY === HEIGHT - 1 && curX === WIDTH - 1){
                result = curCount;
                return;
            }
            
            moves.forEach((move)=>{
                const [dy, dx] = move;
                const [ny, nx] = [curY + dy, curX + dx];
                
                if(getIsVaild(ny, nx)){
                    queue.push([ny, nx, curCount+1]);
                    maps[ny][nx] = 0;
                }
            })
        }
    }
    
    bfs(0, 0);
    
    return result;
}

 

상수를 이용해서 변수를 정의하기

const HEIGHT = maps.length;
const WIDTH = maps[0].length;

나는 처음에 이 부분도  헷갈렸다. 밑에 코드를 보면 getIsValid 쪽에서 조건을 줄 때 이 부분을 사용한다.

처음에는 n과 m으로 변수를 주고 풀었어서 더 헷갈렸던 것 같다.

나는 이때 편협하게.. 어처피 n과 m이 같은 숫자인데 왜 굳이 저렇게 나눌까? 라고 생각을 했었다.

근데 많은 케이스가 있고.. 만약에 5 x 6 과 같은 케이스가 나온다면? 당연히 값이 달라진다.

좀 더 이해가 쉽게 되도록 그림을 그렸다.

만약 5 x 6 과 같은 맵이 있다고 했을 때, maps = [[1, 0, 1, 1, 1] x 6개] 가 될 것이다.

그렇게 치면 maps[0]는 가로의 값이 될 것이고 maps.length가 세로의 값이 될 것이다. 

처음엔 이 부분이 이해가 잘 안되어서 헤맸던 것 같다...

 

상하좌우 좌표 설정하기

두번째로 헷갈렸던 부분... 좌표가 제일 헷갈렸다. 

내가 헷갈렸던 이유는 평면좌표를 생각했을 때 당연히 x축이 가로, 좌우이고 y축이 세로, 상하 인데

도대체 왜 여기선 아래쪽으로 갔을 때 [1, 0] 일까....에 대한 고민을 되게 많이 했다.... 아래로가면 세로축이고 [0, 1] 이 아닌가? 라고 생각했다. 왜냐면 [x, y] 라고 생각했기 때문이다.

이제 이것도 그림을 통해 이해했다.

맵을 (x, y)로 놓고 봤을 때 좌측으로 가면 (1, 1)이 (1, 0)이 된다. 따라서 좌측으로 (0, -1) 만큼 움직인 것이다!! 

그리고 아래쪽으로 가면 (1, 1)이 (2, 1)이 되고 아래로 (1, 0) 만큼 움직인게 된다.

따라서, 상 = [-1, 0] 하 = [1, 0] 좌 = [0, -1] 우 = [0, 1]인 셈이다.

내가 생각한 좌표와 맵에서 보는 것은 다르다!! 이걸 유의하고 풀어야 한다. (처음하면 아마 나처럼 헷갈릴 수도 있다.)

 

bfs 함수 만들기

이제 이 문제의 핵심인 bfs를 만들어보자.

bfs를 풀기 위해선 개념을 알아야하고 queue가 무엇인지도 알아야 한다.

queue는 먼저 들어온 것을 먼저 빼는 방식이다.

queue

이제 코드를 보면 queue 배열 안에 [start, end, 1]을 넣어줬다. 

 const queue = [[start, end, 1]];

 

아까 위에서 말했듯 앞에 있는 좌표 start 가 위아래로 움직이는 좌표, end가 좌우로 움직이는 좌표이다. 

숫자 1은 이동한 거리의 수를 카운팅 하는 것이다. 즉 [0, 0, 1] 이면 현재 캐릭터는 (0, 0)에 있고 이동거리는 1이다.

 

while(queue.length){
            const [curY, curX, curCount] = queue.shift();
            
            if(curY === HEIGHT - 1 && curX === WIDTH - 1){
                result = curCount;
                return;
            }

 이제 while문 내부를 살펴보자. 조건은 queue 배열 길이가 존재할 때까지 반복한다.

현재 queue에는 [start, end, 1] 이라는 요소가 들어가 있고 그부분을 shift()를 이용해 떼온다.

그리고 구조분해할당을 통해서 각각의 변수에 저장해준다.

조건문에서는 각각의 위치값이 배열을 벗어나면 안되므로 조건을 걸어준 것이다.

여기서 -1을 해주는 이유는 칸수로는 5개지만 (0, 0)부터 시작하므로 끝은 (4, 4)이다. 

그리고 그 맵을 벗어나지 않는 범위 한에서 이동할 때마다 카운팅한 수를 결과값에 넣어준다.

 

moves.forEach((move)=>{
                const [dy, dx] = move;
                const [ny, nx] = [curY + dy, curX + dx];
                
                if(getIsVaild(ny, nx)){
                    queue.push([ny, nx, curCount+1]);
                    maps[ny][nx] = 0;
                }
            })

이제 moves에 넣어놨던 상하좌우를 돌면서 이동하고자 하는 방향값인 dy, dx에 값을 넣어준다.

그리고 다음 좌표인 ny, nx에 queue에서 가져온 변수들을 dy, dx와 더해준다.

참고로 좌표문제에서 많이 사용하는 변수인 dx, dy, nx, ny는 각각 deltaX, deltaY (다음 이동하고자 하는 방향 값)
nextX, nextY (다음 좌표)를 의미한다.

 

const getIsValid = (y, x) => {
        if(x >= 0 && y >= 0 && x < WIDTH && y < HEIGHT && maps[y][x] === 1) return true;
    }

그리고 유효성을 검사하는 함수를 하나 만들었다. (조건이 길기때문에 따로 로직을 함수로 분리했다.)

x, y가 0보다 크거나 같고 가로, 세로 보다 작으며 (맵을 벗어나지 않는 조건), maps[y][x]가 1일때(지나갈 수 있는 좌표) trrue을 반환하는 함수이다.

이 함수를 가지고 ny, nx(다음좌표)를 매개변수로 넣어준다. 

그리고 조건문을 만족시키면(true이면) queue에 그 좌표를 다시 넣고 이동거리 + 1 을 한 후 넣어준다.

그리고 그 좌표는 0으로 처리해 이동할 수 없는 공간으로 다시 바꿔준다.

 

마지막으로 bfs 함수를 호출하는데 초기값을 캐릭터가 위치하는 (0, 0)으로 지정 해준다.

그리고 결과값을 반환하면 끝!

 

처음에는 구글에서 찾을 수 있는 방법으로 풀었다. 하지만 가독성이 그닥 좋지않고 변수명이 나를 헷갈리게했다.

리팩토링한 풀이는 bfs라는 함수로 분리하고 상수를 사용해 변수를 명확히 지정했다.

아무래도 나에겐 좀 어려웠던 문제라 직접 그리고 하나하나 대입해보면서 푸니까 나름 이해가 된 것 같다.

나중에 bfs를 활용한 좌표문제를 풀 수도 있으니 미리 기록할 겸 남겨봤다.

그리고 처음 푸는 다른사람들에게도 도움이 되었으면 좋겠다! 

많은 글이 있지만 일일이 풀어써준 글은 별로 없어서..  나중에 나도 또 다시 풀어 볼 예정이다.