[프로그래머스] 게임 맵 최단거리 (Lv 2) - javascript / BFS

📝 문제

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

 

 

문제 더보기

 

🔑 풀이

최단 거리 문제는 BFS(너비 우선 탐색)을 사용해야한다.

현재 위치를 노드로 놓고, 사방을 탐색해서 조건에 맞으면 큐에 저장한다.

그리고 그 큐에서 값을 하나씩 꺼내서 사방을 탐색에서 조건에 맞으면 큐에 저장...

이 과정을 큐에 값이 없어질 때까지 반복하면 된다.

그리고 나아갈 때마다 방문 표시를 하고, 방문하는 칸의 갯수를 세야 한다.

방문 표시 방법과 칸 갯수를 세는 방법에 따라 코드가 조금씩 달라진다.

나는 방문 표시를 위해 따로 배열을 생성하지 않고, 큐에 같이 저장하는 방식을 선택했다.

 

+ x축, y축, row, column을 같이 사용하는 경우 혼동하기 쉬워서 row, column으로 고정했다.

 

1차 풀이

function solution(maps) {
    let moveRow = [-1,0,1,0];
    let moveCol = [0,1,0,-1];
    
    let row = maps.length;
    let column = maps[0].length;
    
    let queue = [[0,0,1]];
    
    while(queue.length) {
        
        let [r,c,cnt] = queue.shift();
        maps[r][c] = 0;
        
        for(let i = 0; i < 4; i++) {
            let nr = r + moveRow[i];
            let nc = c + moveCol[i];
            
            if(nr === row-1 && nc === column-1) return ++cnt;
            
            if(nr >= 0 && nc >= 0 && nr < row && nc < column) {
                if(maps[nr][nc] === 1) {
                    queue.push([nr,nc,cnt+1]);
                }
            }
        }
    }
    return -1;
}

정확도는 통과했으나 효율성을 통과하지 못해서 헤매던 중, '질문하기'의 글을 보고 해결했다.

[Horyong Jung님의 글]

 

 

큐에 저장한 값을 꺼낼 때 방문처리를 했더니,다음 큐의 값으로 순회할 때 저장된 위치임에도 불구하고 또 큐에 저장되는 상황이 발생했다.

큐에 집어넣을 때 방문처리가 되지 않으니... 당연하다

 

2차 풀이

function solution(maps) {
    let moveRow = [-1,0,1,0];
    let moveCol = [0,1,0,-1];
    
    let row = maps.length;
    let column = maps[0].length;
    
    let queue = [[0,0,1]];
    maps[0][0] = 0;
    
    while(queue.length) {
        
        let [r,c,cnt] = queue.shift();
        
        for(let i = 0; i < 4; i++) {
            let nr = r + moveRow[i];
            let nc = c + moveCol[i];
            
            if(nr === row-1 && nc === column-1) return ++cnt;
            
            if(nr >= 0 && nc >= 0 && nr < row && nc < column) {
                if(maps[nr][nc] === 1) {
                    queue.push([nr,nc,cnt+1]);
                    maps[nr][nc] = 0;
                }
            }
        }
    }
    return -1;
}

 

• 풀이 과정

function solution(maps) {
    let moveRow = [-1,0,1,0]; // 남동북서 차례로 움직일 행,열 준비
    let moveCol = [0,1,0,-1];
    
    let row = maps.length; 
    let column = maps[0].length;
    
    let queue = [[0,0,1]]; // BFS의 노드 저장 [row, column, count]
    maps[0][0] = 0; // 출발 위치 방문 표시
    
    while(queue.length) {
        
        let [r,c,cnt] = queue.shift(); // 현 위치에 변수 할당
        
        // 남동북서 방향으로 순회하며 나아갈 수 있는 곳 찾아서 큐에 저장
        for(let i = 0; i < 4; i++) {
            let nr = r + moveRow[i]; // nextRow = 확인할 행 변수 할당
            let nc = c + moveCol[i]; // nextColumn = 확인할 열 변수 할당
            
            if(nr === row-1 && nc === column-1) return ++cnt; // 위치가 도착점이라면, 바로 count+1 반환
            
            if(nr >= 0 && nc >= 0 && nr < row && nc < column) { // 좌표를 벗어나지 않는지 확인
                if(maps[nr][nc] === 1) { // 위치의 값이 1로 나아갈 수 있는지 확인
                    queue.push([nr,nc,cnt+1]); // 나아갈 수 있다면, 큐에 저장
                    maps[r][c] = 0; // 위치 방문 표시 ★
                }
            }
        }
    }
    return -1; // 만약 도착점에 닿을 수 없다면, 위 반복문을 빠져나와서 -1 반환
}

 

• 정확도 테스트 결과

 

• 효율성 테스트 결과

 

 

---

참고

https://takeu.tistory.com/96