프로그래스_Level.2 게임 맵 최단거리

1.문제설명

문제: 게임 맵 최단거리

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

문제 설명은 들어가서 그림과 함께 보고오세요

 

2. 제한 조건

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

3.입출력 예

 

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

 

📌나의 풀이

이 문제를 보자마자 BFS가 생각났다. 자료구조 queue를 사용하여 BFS알고즘을 구현하였다.

queue의 크기가 0이 될 때 까지 while문을 반복한다

queue에서 맨 앞에 값을 뺀후 x와 y에 대입한다.

for문을 4번 돌면서 상 하 좌 우 로 움직였을 때의 값을 구해 nx, ny에 대입한다.

nx,ny가 공간을 벗어난 경우, 0인 경우 무시한다.

해당노드를 처음 방문한 경우에만 maps[y][x]+1 maps[ny][nx] = maps[y][x]+1;을하고 nx,ny를 queue에 push한다.

function solution(maps) {
    
    var h = maps.length;//맵의 열 크기
    var w = maps[0].length;//맵의 행 크기
    var queue = [[0,0]];
    //상 하 좌 우 
    let dy = [-1,1,0,0];
    let dx = [0,0,-1,1];
    
    while(queue.length>0){
        let top = queue.shift();
        let x = top[0];
        let y = top[1];
        
        for(let i=0; i<4; i++){
            let nx = x+dx[i];
            let ny = y+dy[i];
            
            //공간을 벗어난 경우 무시
            if(nx<0 || nx>=w || ny<0 || ny>=h)continue;
            
            //0인 경우 무시
            if(maps[ny][nx]===0)continue;
            
            //해당 노드를 처음 방문하는 경우에만 최단 거리
            if(maps[ny][nx]===1){
                maps[ny][nx] = maps[y][x]+1;
                queue.push([nx,ny])
            }
        }
        
    }
    if(maps[h-1][w-1]===1)return -1; //상대 팀 진영에 도착할 수 없슴
    else return maps[h-1][w-1];
    console.log(maps);
    
}