[프로그래머스] 게임 맵 최단거리(BFS)

아무것도 모르지만 ! 최단거리를 찾는 문제이므로 bfs로 풀어야겠다는 생각을 했습니다 ㅎㅎ

그리고 bfs는 보통 queue를 사용해서 푼다고 하네요!

 

function solution(maps) {
    const n = maps.length; // 맵의 행 길이
    const m = maps[0].length;  // 맵의 열 길이
    const directions = [
        [-1, 0], // 위로 이동
        [1, 0], // 아래로 이동
        [0, -1], // 왼쪽으로 이동
        [0, 1], // 오른쪽으로 이동
    ];
    
    const queue = [];
    queue.push([0, 0, 1]) // 시작 위치와 이동할 거리를 담은 큐 생성
    maps[0][0] = 0; // 방문 한 곳은 0으로 표시
    
    while (queue.length) {
        const [x, y, dist] = queue.shift();
        // 큐에서 추출된 요소의 첫 번째 값이 x에 할당됨(인덱스 0)
        // 큐에서 추출된 요소의 두 번째 값이 y에 할당됨(인덱스 1)
        // 큐에서 추출된 요소의 세 번째 값이 dist에 할당됨(인덱스 2)
        
        // 상대 팀 진영에 도달한 경우 최단 거리를 반환
        if ( x === n - 1 && y === m - 1) {
            return dist;
        }
        
        // 네 방향으로 탐색
        for (const [dx, dy] of directions){
            const nx = x + dx;
            const ny = y + dy;
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] === 1){
                // 캐릭터가 이동 가능한 위치인 경우
                queue.push([nx, ny, dist + 1]);
                maps[nx][ny] = 0; // 방문 한 곳은 0으로 표시해서 중복 방문을 방지
            }
        }
    }
    // 상대 진영에 도달할 수 없는 경우 -1을 반환
    return -1;
}

 

   if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] === 1){

캐릭터가 오른, 아래쪽으로만 이동할 수 있는 경우를 어떻게 처리해야 하는지 고민이었는데, 이렇게 해결하면 됩니다 ! 

• nx >= 0: 다음 이동할 x 좌표 nx가 맵의 왼쪽 끝을 넘어서지 않아야 합니다.
• nx < n: 다음 이동할 x 좌표 nx가 맵의 오른쪽 끝을 넘어서지 않아야 합니다.
• ny >= 0: 다음 이동할 y 좌표 ny가 맵의 위쪽 끝을 넘어서지 않아야 합니다.
• ny < m: 다음 이동할 y 좌표 ny가 맵의 아래쪽 끝을 넘어서지 않아야 합니다.
• maps[nx][ny] === 1: 다음 이동할 위치가 벽이 아니라는 조건입니다.

입력값이 

[[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]] 일때 큐의 변화를 나타내면

1. 큐의 첫 번째 요소를 추출합니다.
   • 큐: [[0, 0, 1]]
   • 추출된 요소: [0, 0, 1] (x: 0, y: 0, dist: 1)
2. 추출된 요소의 위치에서 상하좌우로 이동할 수 있는 위치를 탐색합니다.
   • (0, 0)에서 위, 오른쪽으로 갈 수 있습니다. 그러나 아래, 왼쪽으로는 범위를 벗어납니다.
   • 탐색된 위치: (상: [-1, 0], 하: [1, 0], 좌: [0, -1], 우: [0, 1])
3. 이동 가능한 위치를 큐에 추가합니다.
   • 큐: [[1, 0, 2], [0, 1, 2]]
   • 총 이동한 거리(dist)가 2입니다. 왼쪽 방향으로는 벽(0)이므로 추가되지 않습니다.
4. 큐의 첫 번째 요소를 추출합니다.
   • 큐: [[1, 0, 2], [0, 1, 2]]
   • 추출된 요소: [1, 0, 2] (x: 1, y: 0, dist: 2)
5. 추출된 요소의 위치에서 상하좌우로 이동할 수 있는 위치를 탐색합니다.
   • (1, 0)에서 아래, 오른쪽으로 갈 수 있습니다. 그러나 위, 왼쪽으로는 범위를 벗어납니다.
   • 탐색된 위치: (상: [0, 0], 하: [2, 0], 좌: [1, -1], 우: [1, 1])
6. 이동 가능한 위치를 큐에 추가합니다.
   • 큐: [[0, 1, 2], [2, 0, 3]]
   • 총 이동한 거리(dist)가 각각 2와 3입니다. 위쪽 방향으로는 벽(0)이므로 추가되지 않습니다.
7. 큐의 첫 번째 요소를 추출합니다.
   • 큐: [[0, 1, 2], [2, 0, 3]]
   • 추출된 요소: [0, 1, 2] (x: 0, y: 1, dist: 2)
8. 추출된 요소의 위치에서 상하좌우로 이동할 수 있는 위치를 탐색합니다.
   • (0, 1)에서 위, 오른쪽으로 갈 수 있습니다. 그러나 아래, 왼쪽으로는 범위를 벗어납니다.
   • 탐색된 위치: (상: [-1, 1], 하: [1, 1], 좌: [0, 0], 우: [0, 2])
9. 이동 가능한 위치를 큐에 추가합니다.
   • 큐: [[2, 0, 3], [1, 1, 3]]
   • 총 이동한 거리(dist)가 각각 3입니다. 왼쪽 방향으로는 벽(0)이므로 추가되지 않습니다.
10. 큐의 첫 번째 요소를 추출합니다.

• 큐: [[2, 0, 3], [1, 1, 3]]
• 추출된 요소: [2, 0, 3] (x: 2, y: 0, dist: 3)

1. 추출된 요소의 위치에서 상하좌우로 이동할 수 있는 위치를 탐색합니다.

• (2, 0)에서 아래로 갈 수 있습니다. 위, 오른쪽, 왼쪽으로는 범위를 벗어납니다.
• 탐색된 위치: (상: [1, 0], 하: [3, 0], 좌: [2, -1], 우: [2, 1])

1. 이동 가능한 위치를 큐에 추가합니다.

• 큐: [[1, 1, 3], [3, 0, 4]]
• 총 이동한 거리(dist)가 각각 3과 4입니다. 위쪽 방향으로는 벽(0)이므로 추가되지 않습니다.

1. 큐의 첫 번째 요소를 추출합니다.

• 큐: [[1, 1, 3], [3, 0, 4]]
• 추출된 요소: [1, 1, 3] (x: 1, y: 1, dist: 3) .......

이런 식으로 작동합니다 !