[프로그래머스] 게임 맵 최단거리 Javascript

[프로그래머스] 게임 맵 최단거리 Javascript

문제 내용

maps 배열이 주어짐.(0, 0) 에서 출발해서 (n -1, m-1) 까지 최단거리를 찾아라.최단거리가 없다면 -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) 위치에 있습니다.

전체 코드

function solution(maps) { // 1. n 과 m 을 설정함 const n = maps.length; const m = maps[0].length; // 2. 정답 저장용 let answer = -1; // 3. 방문을 체크할 배열 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 = [-1, 0, 1, 0]; const moveY = [0, 1, 0, -1]; // 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 < moveX.length; i++) { // 17. movedX, Y 로 설정함. const movedX = x + moveX[i]; const movedY = y + moveY[i]; // 18. 만약, movedX, movedY 가 배열의 범위 안에 있고, 그 값 위치가 아직 방문하지 않았고, 그 위치를 방문할 수 있다면 (값이 1이라면) if (movedX >= 0 && movedX < n && movedY >= 0 && movedY < m && !visited[movedX][movedY] && maps[movedX][movedY] == 1) { // queue 에 그 값을 넣음 queue.push([x + moveX[i], y + moveY[i], count + 1]); } } } return answer; }

문제의 첫번째 예시를 보면

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

이렇게 주어졌다.

그림으로 보면

이런 식의 모양이다.

// 3. 방문을 체크할 배열 let visited = Array.from(Array(n), () => Array(m).fill(false));

maps 와 동일한 크기로 visited 배열을 생성해주었다.

// 4. BFS 를 하기 위한 queue, 초기 값을 저장해둠 let queue = [[0, 0, 1]]; // 5. queue 의 위치를 저장할 queueIndex let queueIndex = 0; // 6. x, y 가 움직일 배열을 저장함 (상, 우, 하, 좌) const moveX = [-1, 0, 1, 0]; const moveY = [0, 1, 0, -1];

그리고 queue 에 초기 값을 넣어주고 해당 queue 의 위치를 나타낼 queueIndex.

또 상, 우, 하, 좌 방향으로 x, y 를 움직일 moveX, moveY 도 만들어줬다.

// 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]) } }

queue 에는 현재 [[0, 0, 1]] 이므로 length 는 1 이고 queueIndex 는 0 이므로 while 문이 진행된다.

먼저 now 값은 [0, 0, 1] 이 되고

queueIndex 를 + 1 해준다.

0, 0 은 n - 1, m - 1 이 아니므로 12번이 진행된다.

// 14. 방문 함수. x, y 좌표와 count (이동거리) 를 파라미터로 받음 function visit(x, y, count) { // 15. 먼저 방문했다고 체크함 visited[x][y] = true; // 16. 현재 x, y 위치에서 상, 하, 좌, 우 로 이동할 반복문 for (let i = 0; i < moveX.length; i++) { // 17. movedX, Y 로 설정함. const movedX = x + moveX[i]; const movedY = y + moveY[i]; // 18. 만약, movedX, movedY 가 배열의 범위 안에 있고, 그 값 위치가 아직 방문하지 않았고, 그 위치를 방문할 수 있다면 (값이 1이라면) if (movedX >= 0 && movedX < n && movedY >= 0 && movedY < m && !visited[movedX][movedY] && maps[movedX][movedY] == 1) { // queue 에 그 값을 넣음 queue.push([x + moveX[i], y + moveY[i], count + 1]); } } }

일단 이렇게 시작을 한다.

0, 0 을 방문했다고 체크를 하고 (15 번)

현재 위치에서 이동할 수 있는 지 확인하고 이동할 수 있다면 queue 에 값을 집어넣는다.

queue 에 [1, 0, 2] 가 저장되었고 visited[0][0] = true 가 된 모습이다.

동일하게 진행하면 visit(2, 2, 7) 이 불리고

저장할 때 상, 우, 하, 좌 순으로 저장 (6번) 을 하기 때문에

이렇게 저장이 되어있다면

[1, 2, 8] 먼저 진행하고 그 다음에 [2, 3, 8] 을 진행한다.

쭉 진행하게 되면

[3, 4, 10] 이 진행이 되고

그 다음에 [0, 4, 11], 그리고 [4, 4, 11] 진행되면서 10 번 (now[0], [1] = n-1, m-1) 이 해당하면서

answer 에 답을 갱신하고 종료된다.

결론

BFS 로 쉽게 풀 수 있다.

상, 우, 하, 좌 순으로 반복하는 것 보다 우, 하 를 먼저 반복하는게 더 시간이 짧게 걸리지 않을까 생각한다. (목적지가 우측 하단에 있으므로??)

상, 우, 하, 좌 순 하, 우, 좌, 상 순

별 차이 없는 듯

출처 : 프로그래머스 찾아라 프로그래밍 마에스터 게임 맵 최단거리

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

from http://hogumachu.tistory.com/9 by ccl(A) rewrite - 2021-10-06 16:01:13