프로그래머스 JS [게임 맵 최단거리]⭐ BFS/큐/최단거리

게임 맵 최단거리 문제보기

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

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

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

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

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

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

게임 맵의 상태 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) 위치에 있습니다.

---

입출력 예mapsanswer

[[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

---

큐가 무엇이냐 Queue는 먼저 들어온 것이 먼저 나가요. 놀이기구를 탑승하기 위해 줄을 설 때, 줄에 먼저 선 사람이 먼저 탑승하는 것과 같습니다. a, b, c 순서대로 들어왔다면 [] [a] [a,b] [a,b,c]  a, b, c 순서대로 일을 처리합니다. [b,c] [c] []

n*m 미로를 이동하는 게임 코드 설명 이동 // 주변의 길 중에서 이동가능한 방향 (1) 찾기 // ㄴ이동한 좌표 0으로 바꾸기 // ㄴ해당 칸으로 player 이동하기 // ㄴ이동 횟수 +1 하기 목표 // 또는 n-1,m-1에 도달할 때까지 이동하기 (성공: 이동 거리 반환) // 더이상 이동할 수 없을 때까지 이동하기 (실패 : -1 반환) 1) 미로의 가로 크기는 n, 세로 크기는 m에 저장합니다.     const n = maps.length;     const m = maps[0].length; 2) 상하좌우 중 이동이 가능한 방향으로 이동하기 위한 커맨드를 저장합니다.     const command = [         [0, -1],         [0, 1],         [-1, 0],         [1, 0],     ]; 3) 플레이어의 x좌표, y좌표, 이동한 횟수를 저장할 변수를 만듭니다.     let player = [[0, 0, 0]]; 4) 게임 종료 조건을 정합니다.     while (player.length > 0) {         // 출구(n-1,m-1)에 도달하면 게임 승리         if (x === n - 1 && y === m - 1) {             return moveCount + 1;         }         // 플레이어가 모든 움직임을 수행하여도 도달할 수 없다면 막힌 미로         if (player.length === 0) {             return -1;         }     } 5) 현재 플레이어의 x좌표, y좌표, 이동한 횟수를 가져옵니다.     while (player.length > 0) {         // 현재 x좌표, y좌표, 이동 횟수         const [x, y, moveCount] = player.shift(); 6) 상하좌우로 이동을 시도할 것입니다. 현재 x좌표와 y좌표에, 이동할 x좌표와 y좌표를 더해줍니다.         // 상하좌우 움직임 저장         command.forEach((move) => {             // 현재 x,y좌표 + 움직일 x,y좌표             const xMove = x + move[0];             const yMove = y + move[1]; ex)  [0,0] + [0,1] 아래로 이동 [0,0] + [0,-1] 위로 이동 [0,0] + [-1,0] 왼쪽으로 이동 [0,0] + [1,0] 오른쪽으로 이동 7) 미로 내에서만 움직이도록 조건을 정합니다. xy좌표는 마이너스 좌표가 없고, 미로보다 큰 좌표로 이동할 수 없습니다.             // 미로 경계 안에서             if (xMove >= 0 && yMove >= 0 && xMove < n && yMove < m) {   8) 이동이 가능한 지역(1이 표시된 좌표)을 찾습니다.  이동을 했다면 해당 좌표의 1을 0으로 바꿔 이동 흔적을 남깁니다. 이동한 좌표를 저장합니다. 이동 횟수를 +1 하여 저장합니다.                 // 이동 가능한 지역이라면                 if (maps[xMove][yMove] === 1) {                     // 이동을 하고 지나간 자리에는 흔적을 남김                     maps[xMove][yMove] = 0;                     // 이동한 x,y좌표 저장, 이동한 횟수 +1                     player.push([xMove, yMove, moveCount + 1]);                 }             }         }); 9) 게임이 종료되지 않았다면, 다시 이동을 합니다.   => 5) 현재 플레이어의 x좌표, y좌표, 이동한 횟수를 가져옵니다.     while (player.length > 0) {         // 현재 x좌표, y좌표, 이동 횟수         const [x, y, moveCount] = player.shift(); queue에 저장된 좌표이동 예시는 전체 코드 아래에 남김.

function solution(maps) {     const n = maps.length;     const m = maps[0].length;     const command = [         [0, -1],         [0, 1],         [-1, 0],         [1, 0],     ];     let player = [[0, 0, 0]];     while (player.length > 0) {         // 현재 x좌표, y좌표, 움직임 횟수         const [x, y, moveCount] = player.shift();         // 출구(n-1,m-1)에 도달하면 게임 승리         if (x === n - 1 && y === m - 1) {             return moveCount + 1;         }         // 상하좌우 움직임 저장         command.forEach((move) => {             // 현재 x,y좌표 + 움직일 x,y좌표             const xMove = x + move[0];             const yMove = y + move[1];             // 미로 경계 안에서             if (xMove >= 0 && yMove >= 0 && xMove < n && yMove < m) {                 // 이동 가능한 지역이라면                 if (maps[xMove][yMove] === 1) {                     // 이동을 하고 지나간 자리에는 흔적을 남김                     maps[xMove][yMove] = 0;                     // 이동한 x,y좌표 저장, 움직임 횟수 +1                     player.push([xMove, yMove, moveCount + 1]);                 }             }         });         // 플레이어가 모든 움직임을 수행하여도 도달할 수 없다면 막힌 미로         if (player.length === 0) {             return -1;         }     } } // 이동 // 주변칸 중에 1 찾기 // 더이상 이동할 수 없을 때까지 or n-1,m-1에 도달할 때까지 이동하기 // ㄴ이동할 좌표 0으로 바꾸기 // ㄴ해당 칸으로 player 이동하기 // 목표: 1,1 에서 n-1,m-1 으로 가기 solution([     [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], ]);

좌표이동 예시 [ x좌표, y좌표, 이동횟수 ] [   [ 0, 0, 1, 1, 1 ],   [ 1, 0, 1, 0, 1 ],   [ 1, 0, 1, 1, 1 ],   [ 1, 1, 1, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 0, 0, 0 ] ] 00 => 10 [    [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 1, 0, 1, 1, 1 ],   [ 1, 1, 1, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 1, 0, 1 ] ]  10 => 20 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 0, 0, 1, 1, 1 ],   [ 1, 1, 1, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 2, 0, 2 ] ] 20 => 30 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 0, 0, 1, 1, 1 ],   [ 0, 1, 1, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 3, 0, 3 ] ] 30 => 31 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 3, 1, 4 ] ] 31 => 32 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 3, 2, 5 ] ] 32 => 22 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 1, 0, 1 ],   [ 0, 0, 0, 1, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 2, 2, 6 ] ] 22 => 23, 12 두 곳으로 이동 가능 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 2, 3, 7 ], [ 1, 2, 7 ] ] 23 => 24 [   [ 0, 0, 1, 1, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 1, 2, 7 ], [ 2, 4, 8 ] ] 12 => 02 [   [ 0, 0, 0, 1, 1 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 2, 4, 8 ], [ 0, 2, 8 ] ] 24 => 14, 34 두 곳으로 이동 가능 [   [ 0, 0, 0, 1, 1 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 0, 2, 8 ], [ 1, 4, 9 ], [ 3, 4, 9 ] ] 02 => 14 [   [ 0, 0, 0, 0, 1 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 1, 4, 9 ], [ 3, 4, 9 ], [ 0, 3, 9 ] ] 14 => 04 [   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 1 ] ] ------ [ [ 3, 4, 9 ], [ 0, 3, 9 ], [ 0, 4, 10 ] ] 34 => 44 목표 지점으로 이동함 [   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ] ] ------ [ [ 0, 3, 9 ], [ 0, 4, 10 ], [ 4, 4, 10 ] ]  03 => X 이동 불가 [   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ] ] ------ [ [ 0, 4, 10 ], [ 4, 4, 10 ] ] 04 => X, 44 => 목표지점 이동횟수 count 10 반환되고 종료 [   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ],   [ 0, 0, 0, 0, 0 ], ]  X, 목표지점 이동횟수 count 10 반환되고 종료 => 큐에 남아있는 이동 없음