프로그래머스 - 게임 맵 최단거리

 

<문제>

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

프로그래머스

 

<문제 핵심>

1. BFS

✅ 카테고리를 보기 전부터 최단 거리를 구하는 문제의 의도를 파악하는 순간 BFS 알고리즘을 사용하자 라고 접근 방향을 정하였다. 백준 js 15649번 문제 블로그에서 bfs를 정리 했었는데 이번 문제를 통해 다시 복기할 수 있었다.

참고: https://no2jfamily.tistory.com/47

백준 js 15649번

 

2. BFS 탐색 중에 이미 방문한 위치를 다시 방문하지 않도록 하기

✅ 1이면 움직일 수 있고 0이면 움직일 수 없다. 이미 방문한 위치의 재방문을 막고자 0으로 설정(백 트래킹 알고리즘 과의 차이)

maps[newRow][newCol] = 0;

 

<문제 풀이과정 및 순서도>

1. 행, 열 갯수 그리고 maps 배열에서 동,서,남,북으로 움직이기 위한 방향 벡터를 만든다.

let n = maps.length; // 행의 개수
let m = maps[0].length; // 열의 개수
let dir = [[-1, 0],[1, 0], [0, -1], [0, 1]];

 

2. bfs 함수 로직을 구현한다.

✅ 시작 위치도 거리의 길이를 잴 때 포함되기 때문에 초기 거리를 1로 설정해준다.(queue = [[0, 0, 1]] )

✅ 행/열이 종착지와 동일하다면 그때의 distance를 return한다.

✅ 문제 조건에 의거하여 맵을 벗어나지 않으면서 이동할 수 있는 위치라면 이동한 위치와 현재 거리 + 1을 큐에 넣는다. 그리고 이동한 위치의 재방문을 방지하고자 0으로 설정해준다.

✅ 상대팀 진영에 도착 할 방법이 없다면 -1을 리턴한다.

const bfs = () => {
        const queue = [[0,0,1]];
        maps[0][0] = 0;
        
        while(queue.length > 0) {
            const [row, col, distance] = queue.shift();
            if(row === n-1 && col === m-1) {
                return distance;
            }
            
            for(let [r, c] of dir) {
                let newRow = r + row;
                let newCol = c + col;
                
                if(newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && maps[newRow][newCol] === 1) {
                    queue.push([newRow,newCol,distance+1])
                    maps[newRow][newCol] = 0;
                }
            }
        }
        
        return -1;
}

 

<전체 코드>

function solution(maps) {
    let n = maps.length; // 행의 개수
    let m = maps[0].length; // 열의 개수
    let dir = [[-1, 0],[1, 0], [0, -1], [0, 1]];
    
    const bfs = () => {
        const queue = [[0,0,1]];
        maps[0][0] = 0;
        
        while(queue.length > 0) {
            const [row, col, distance] = queue.shift();
            if(row === n-1 && col === m-1) {
                return distance;
            }
            
            for(let [r, c] of dir) {
                let newRow = r + row;
                let newCol = c + col;
                
                if(newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && maps[newRow][newCol] === 1) {
                    queue.push([newRow,newCol,distance+1])
                    maps[newRow][newCol] = 0;
                }
            }
        }
        
        return -1;
    }
    return bfs();
}