[JS] 게임맵 최단거리 - 미뤄뒀던 BFS에 대해

이 문제는 정말 정석적인 재귀함수 문제입니다.

뭔가 계속 관성적으로 dfs를 쓰다보니 (사실 bfs는 큐를 사용하기 때문에 생각하기 싫은 것도 있었어요.)

효율성 테스트가 통과가 안되더라구요.

일단 같이 한번 풀어봐요!

 

문제 요약

게임을 하려고 합니다.

[0, 0]에서 좌표의 끝지점까지 가는 최소 거리를 구해주세요!

 

문제 해석

전 처음에 dfs를 사용했습니다.

항상 dfs 사용할 때 return 값때문에 뭔가 잘 생각이 팍 안나는 편인데 다른 분들 코드에서 영감을 얻어서 solution 함수 안에 구현해줬는데요. 일단 dfs 코드 먼저 보시죠.

 

정답 코드(DFS)

function check (row, col, maxRow, maxCol) {
    if (row < 0 || col < 0 || row === maxRow || col === maxCol) return false;
    return true;
}

function solution(maps) {
    const orgVisited = Array.from({length: maps.length}, (_, i) => maps[i].map(v => v === 0));
    const answer = [];
    dfs(0, 0, maps, orgVisited, 1);
    return answer.length === 0 ? -1 : Math.min(...answer);
    
    function dfs(row, col, maps, visited, length) {
        const [maxRow, maxCol] = [maps.length, maps[0].length];
        if (row === maxRow - 1 && col === maxCol - 1) {
            answer.push(length);
            return ;
        }
        const dx = [-1, 0, 1, 0];
        const dy = [0, -1, 0, 1];
        for (let i = 0; i < 4; i++) {
            const nextR = row + dy[i];
            const nextC = col + dx[i];
            if (check(nextR, nextC, maxRow, maxCol)) {
                const nextVisit = visited.map(v => [...v]);
                if (!nextVisit[nextR][nextC]) {
                    nextVisit[row][col] = true;
                    dfs(nextR, nextC, maps, nextVisit, length + 1);
                }
            }
        }
    }
}

채점 결과

• 정확성: 69.9
• 효율성: 0.0
• 합계: 69.9 / 100.0

 

이유를 잘 찾아봤더니 최소거리는 bfs를 사용해야한다고 합니다.

재귀함수는 메모리 스택 구조를 사용하기 때문에 bfs로 구현하기 위해서는 별도의 큐를 만들어준 다음, while 문 등을 통한 반복으로 처리해나가야합니다. 

 

정답 코드(BFS)

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(val) {
        this.queue[this.rear++] = val;
    }
    
    dequeue() {
        const val = this.queue[this.front++];
        return val; 
    }
    
    size() {
        return this.rear - this.front;
    }
    
    isEmpty() {
        return this.rear === this.front;
    }
}

function check (row, col, maxRow, maxCol) {
    if (row < 0 || col < 0 || row === maxRow || col === maxCol) return false;
    return true;
}

function solution(maps) {
    const orgVisited = Array.from({length: maps.length}, (_, i) => maps[i].map(v => v === 0));
    const answer = [];
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, -1];
    const [maxRow, maxCol] = [maps.length, maps[0].length];
    const queue = new Queue();
    queue.enqueue([0, 0, 1]);
    orgVisited[0][0] = true;
    while (!queue.isEmpty()) {
        const [row, col, length] = queue.dequeue();
        for (let i = 0; i < 4; i++) {
            const [nextR, nextC] = [row + dy[i], col + dx[i]];
            if (check(nextR, nextC, maxRow, maxCol)) {
                if (!orgVisited[nextR][nextC]) {
                    if ((nextR === maxRow - 1) && (nextC === maxCol - 1)) {
                        return length + 1;
                    }
                    queue.enqueue([nextR, nextC, length + 1]);
                    orgVisited[nextR][nextC] = true;
                }
            }
        }
    }
    return -1;
}

오늘 이제 bfs를 공부하면서 몇 개 팁이 생겨서 공유해보려고 합니다.

팁 1. visited의 공유에 대해서

bfs는 최단 거리를 찾기에 적합하지만, visited를 조작할 때는 이야기가 다릅니다.

// [0][3]과 [3][4]를 유의깊게 봐주세요.
[
  [ true, true, true, false, false ],
  [ true, true, true, true, false ],
  [ true, true, true, true, true ],
  [ true, true, true, true, false ],
  [ true, true, true, true, false ]
]
[
  [ true, true, true, false, false ],
  [ true, true, true, true, true ],
  [ true, true, true, true, true ],
  [ true, true, true, true, true ],
  [ true, true, true, true, false ]
]
[
  [ true, true, true, true, false ],
  [ true, true, true, true, true ],
  [ true, true, true, true, true ],
  [ true, true, true, true, true ],
  [ true, true, true, true, false ]
]
...

아시겠지만, 노드의 분기가 생길 때 그 경로를 같은 깊이로 실행하는게 bfs이기 때문에 visited에 쓸데 없는 조작이 들어갑니다.

여기에서 파생되는 문제가 현재까지의 길이를 밖으로 빼는순간 현재 경로의 길이를 파악할 수 없게 된다는 점입니다.

저도 잠깐 고민하다가 그냥 큐에 넣어주는 배열의 3번째 값으로 길이를 넣어주면서 해결했습니다.

 

사실 팁 2로 길이 넣어주는걸 말씀드리려했는데 1이랑 이어져버리네요.

간만에 재귀함수하려니 머리가 아프네요.

 

그럼 이만!