⚡게임 맵 최단거리

깊이/너비 우선 탐색(DFS/BFS)

문제 설명

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

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

최단거리1_sxuruo.png

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

최단거리2_hnjd3b.png

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

최단거리3_ntxygd.png

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

최단거리4_of9xfg.png

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.

  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.

• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

입출력 예

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

입출력 예 설명

입출력 예 #1 주어진 데이터는 다음과 같습니다.

최단거리6_lgjvrb.png

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

최단거리2_hnjd3b (1).png

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2 문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

코드

스스로 해결하지 못하고 찾아본 풀이 코드. 참고, 참고2

✅ 최단 거리, 최소횟수, 미로 탐색 등을구하는 문제는 BFS (너비 탐색) 형제 노드 탐색을 통해 찾아야 한다.

function solution(maps) {
  // maps의 가로, 세로 길이
  const xLen = maps[0].length;
  const yLen = maps.length;

  // 도착 지점의 좌표
  const goalY = yLen - 1;
  const goalX = xLen - 1;

  // 상하좌우 이동 시 칸 수
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, 1, -1];

  const queue = [[0, 0, 1]]; // 현재 위치

  while (queue.length) {
    const [curY, curX, move] = queue.shift(); // 맨 앞에 값을 제거
    if (curY === goalY && curX === goalX) return move;

    for (let i = 0; i < 4; i++) {
      // 현재 위치에서 차례대로 좌, 우, 상, 하 이동 시도
      const ny = curY + dy[i];
      const nx = curX + dx[i];
     
      // 이동하려는 좌표가 (1) 맵을 벗어나지 않으면서 (0 보다 커야함)
      // (2) 이동 가능하다는 뜻인 1의 값을 가지고 있다면
      if (ny >= 0 && ny < yLen && nx >= 0 && nx < xLen && maps[ny][nx] === 1) {
        queue.push([ny, nx, move + 1]);
        maps[ny][nx] = 0; // 이동한 뒤, 해당 칸은 다시 밟지 않도록 0으로 변경
      }
    }
  }

  return -1;
}

function solution(maps) {
    // maps는 n x m 크기로 이루어져 있다.
    // 1. n과 m을 설정
    const n = maps.length;
    const m = maps[0].length;
    
    // 2. 정답 저장용: 최단 거리 경우의 수
    let answer = -1;
    
    // 3. maps와 동일한 크기의 배열을 생성 → 방문 여부 체크할 배열
    let visited = Array.from(Array(n), () => Array(m).fill(false));
    
    // 4. BFS를 하기위한 queue, 초기값을 저장해둠
    let queue = [[0,0,1]];
    
    // 5. queue의 위치를 저장한 queueIndex
    let queueIndex = 0;
    
    // 6. x,y 가 움직일 배열을 저장함 (상,하,좌,우)
    const moveX = [0, 0, -1, 1];
    const moveY = [1, -1, 0, 0];
    
    // 7. BFS를 진행할 while문
    while(queue.length > queueIndex) {
        // 8. 일단 queue에 있는 값을 꺼냄
        const now = queue[queueIndex];
        // 9. 값을 꺼냈으므로 index를 +1 해줌
        queueIndex += 1;
        
        // 10. 만약 꺼낸 값이 정답(도착지)이면
        if(now[0] == n-1 && now[1] == m-1) {
            // 11. answer에 답을 저장함 (now[2]는 이동거리)
            answer = now[2];
            break;
        }
        
        // 12. 만약 꺼낸 값이 방문하지 않은 값이라면
        if(!visited[now[0]][now[1]]) {
            // 13. 현재 좌표값을 방문 체크 배열에 넣기
            visit(now[0], now[1], now[2])
        }
    }    
    
    // 14. 방문 함수. x, y 좌표와 이동거리 count를 파라미터로 받는다.
    function visit(x, y, count) {
        // 15. 먼저, 방문했다고 체크함
        visited[x][y] = true;
        
        // 16. 현재 x, y위치에서 상,하,좌,우로 이동할 반복문
        for(let i = 0; i < 4; i++) {
            // 17. movedX, Y로 설정함
            const movedX = x + moveX[i];
            const movedY = y + moveY[i];
            
            // 18. 만약 movedX, movedY가
            // (1) 배열의 범위 안에 있고,
            // (2) 그 값 위치가 아직 방문하지 않았고,
            // (3) 그 위치를 방문할 수 있다면 (값이 1이라면)
            if (movedX >= 0 && movedX < n && movedY >= 0 && movedY < m && !visited[movedX][movedY] && maps[movedX][movedY] == 1) {
                // queue에 그 값을 넣음
                queue.push([movedX, movedY, count+1]);
            }
        }
    }
    return answer;
}