[프로그래머스 레벨2] 게임 맵 최단거리 [Javascript/ BFS]

부제 : VISITED 배열로 최솟 값 찾기

 

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

프로그래머스

 

문제 접근

최단 거리로 목적지에 도착하는 BFS 문제입니다. 그래서 큐를 사용해서 이동할 방향을 넣어주었습니다.

우리가 필요한 건 저 빨간색 지점(배열의 가장 모서리)에 도착했을 때의 최솟 STEP 수를 세어주면 된다.

아래의 그림을 살펴보자

아래의 그림을 보면 마지막 지점에 도착하는 방법은 여러 방법이 있다.

7 지점에서 위하고 오른쪽에 접근할 수 있는데 사실 중요한건 두 지점의 이동 횟수는 똑같다.

따라서 저 배열의 마지막 인덱스 값에 값이 가장 먼저(빨리) 존재할 때 그 값은 최솟 이동 횟수 값이 된다.

       if(visited[ny][nx] !== 0) continue;
                queue.push([nx, ny]);
                visited[ny][nx] = visited[y][x] + 1;
        }

코드에서 이동하는 자리에 값이 없을 때만 이동하게 한다. (먼저 값을 차지 하고 있으면 돌아서 가는 경우 갱신 안 됨)

자리에 값이 들어가는 최초 순간이 그 자리 이동 최솟값이 된다.

 

 count = visited[maps.length - 1][maps[0].length - 1];

배열의 마지막 인덱스에 값이 도착 최소 이동 값이다.

 

효율성 테스트 까지 통과했다.

 

더 최적화 시키는 방법?

만약 이 문제를 더 최적화 시킨다면 처음 BFS를 하기 전에 마지막 부분 위, 왼쪽에 벽이 있는지 유무를 먼저 체크한다.

 

접근 가능한지 선 체크 후 BFS 

위의 그림같이 아예 벽으로 막힌 상태라면 -1을 반환하고 while문에 들어가지 않는 방법이다.

 if(maps[maps.length - 1][maps[0].length - 2] === 0 && maps[maps.length - 2][maps[0].length - 1] === 0) return -1;

 

 

전체 코드

// 최단거리 bfs
// visited 방문 배열 (한 번 방문 한 곳 다시 방문 X) 
function solution(maps) {
    let count = 0;
    const visited = Array(maps.length).fill(0).map(()=> Array(maps[0].length).fill(0))
    // 오, 왼, 위, 아래 
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    // 가로 , 세로
    let n = maps[0].length;
    let m = maps.length;
    let queue = [];
    queue.push([0,0]);
    visited[0][0] = 1;
    while(queue.length > 0){
        let [x, y] = queue.shift();
        for(let i = 0; i < dx.length; i++){
          let nx = x + dx[i];
          let ny = y + dy[i];
            // (등호주의) 등호를 안 붙여서 방향 이동이 안 되었다.
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || maps[nx][ny] === 0) continue;
            // if(visited[nx][ny] !== 0) 와 if(visited[nx][ny]) 동일
            // visited[nx][ny] === 0 실수로 maps[nx][ny] === 0 이라 써서 오류 생겼음.
            if(visited[nx][ny]) continue;
                queue.push([nx, ny]);
                visited[nx][ny] = visited[x][y] + 1;
        }
    }
    count = visited[maps.length - 1][maps[0].length - 1];
    // count=0 할당 후 !count 와 count === 0 동일
    if(!count) return -1;
    return count;
}

 

주석 제거

function solution(maps) {
    var answer = 0;
    let n = maps.length;
    let m = maps[0].length;
    let visited = new Array(n).fill().map(e => new Array(m).fill(0));
    
    const queue = [];
    queue.push([0,0]);
    visited[0][0] = 1;
    const dirs = [[0,-1],[0,1],[1,0],[-1,0]];
    
    while(queue.length > 0){
        let cur = queue.shift();
        for(let dir of dirs){
            let nx = cur[0] + dir[0];
            let ny = cur[1] + dir[1];
            
            if(nx < 0 || ny < 0 || nx >= n || ny >= m || maps[nx][ny] === 0) continue;
            if(visited[nx][ny] > 0 ) continue;
            
            queue.push([nx,ny]);
            visited[nx][ny] = visited[cur[0]][cur[1]] + 1;
        }
        
       answer = visited[n-1][m-1] > 0 ? visited[n-1][m-1] : -1 ; 
    }
    
    return answer;
}