[프로그래머스] 게임 맵 최단거리 - 자바스크립트(JavaScript)

문제 파악

 게임 맵 최단거리 문제는 깊이/너비 우선 탐색(DFS/BFS) 카테고리에 해당되며 최단거리를 구해야 하므로 BFS(Breadth First Search) 방식으로 해결 할 수 있었다.

 

 우선 BFS란 너비 우선 탐색으로 대표적인 그래프 탐색 방법 중 하나이다. 정점의 자식들을 먼저 탐색하는 방식인 DFS와 다르게 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식이다.

 

 루트(root)와 가까운 노드들 부터 탐색하기 때문에 최단거리를 구할 때 유용하다. 추가적인 특징으로 두 가지의 큐(Queue)를 사용해야하며 DFS 방식보다 메모리가 많이 사용된다.

 

풀이 과정

1. 현 지점에서 다음 차례에 갈 수 있는 지점을 리턴하는 함수 만들기

 다음의 경우를 제외한 좌표값을 반환하도록 만들었다.

• 이미 지나온 지점
• 갈 수 없는 지점
• 맵을 벗어나는 지점

2. 두 가지 Queue를 이용하여 지나온 지점과 다음 차례에 갈 지점들을 계산

 tmpQue에 인접한 노드의 좌표들을 저장하며 tmpQue의 길이가 0이 될 때까지 반복문(while)을 돌렸다.

 

 또한 매 루프마다 history라는 Object에 [0, 0] 부터 시작하여 지나온 지점들을 계층 레벨에 따라 정리하였다.

 

 결국 도달가능한 모든 지점을 순회하다보면 최종 도착 지점의 좌표가 등장하거나 tmpQue의 길이가 0이되어(경로 없음) 반복문이 끝날 것이다.

 

최종 코드

const direction = [[1,0], [0,-1], [-1,0], [0,1]]
function searchPossiblePosition(nowP, beforeP, maps, n, m) {
    var possible = [];
    if(nowP[0] === 0 && nowP[1] === 0){
        var exceptDirection = [0, 0]
    } else {
        var exceptDirection = [beforeP[0] - nowP[0], beforeP[1] - nowP[1]];
    }
    direction.forEach((value) => {
        if(value[0] !== exceptDirection[0] || value[1] !== exceptDirection[1]){
            var tmp = [nowP[0] + value[0], nowP[1] + value[1]]
            if(tmp[0] >= 0 && tmp[1] >= 0 && tmp[0] < n && tmp[1] < m){
                if(maps[tmp[0]][tmp[1]] === 1 && tmp[0] >= 0 && tmp[1] >= 0){
                    possible.push(tmp)
                }
            }
        }
    })
    return possible
}

function solution(maps) {
    var answer = 0;
    var debth = 0;
    var beforeP = [0, 0];
    var visitedQue = [[0, 0]];
    var tmpQue = [[0, 0]];
    var history = {
        '1' : [[0, 0]],
    }
    var isRepeat = 1
    var isArrived = 0
    const n = maps.length
    const m = maps[0].length
    while(!isArrived){
        debth++;
        history[debth+1] = []
        history[debth].forEach((tmp) => {
            searchPossiblePosition(tmp, beforeP, maps, n, m).forEach((value) => {
                tmpQue.forEach((v) => {
                    if(v[0] === value[0] && v[1] === value[1]) {
                        isRepeat = 0
                    }
                })
                if(isRepeat){
                    tmpQue.push(value)
                    history[debth+1].push(value)
                    visitedQue.push(value)
                }
                isRepeat = 1
                maps[tmp[0]][tmp[1]] = 2
                if(value[0] === n - 1 && value[1] === m - 1){
                    isArrived = 1
                }
            })
            tmpQue.shift()
        })
        if(tmpQue.length === 0){
            isArrived = -1
        } else {
            beforeP = tmpQue[0]
        }
        
    }
    
    if(isArrived === 1){
        answer = debth + 1;
    } else {
        answer = -1
    }
    return answer;
}

후기

 문제를 풀고 난 뒤 다른 사람들의 풀이를 볼 수 있었는데, 나의 풀이가 많이 부족하다는 것을 다시 한번 알게 되었다. 다른 DFS, BFS 와 관련된 문제들을 더 풀어보며 연습해야겠다.