-
프로그래머스 - 게임 맵 최단거리Algorithm 2023. 5. 30. 13:22
문제
풀이
큐에 x, y의 좌표값과 방문한 칸의 개수 answer을 초기값으로 각각 0, 0, 1씩 넣어준다
큐에 현재 좌표의 상하좌우의 좌표값과 answer+1이 든 배열을 push해준다
shift()로 큐에서 하나씩 빼내서 해당 좌표가 갈 수 없는 길이라면 다음 요소를 확인하고 갈 수 있는 길이라면 큐에 남은 요소가 없어질 때 까지 이 과정을 반복한다
반복하는 과정중 x, y 좌표가 상대 진영에 도달하면 answer을 리턴한다
큐에 남은 요소가 없어진다면 상대 진영에 도착하지 못한다는 의미이기에 -1을 리턴한다
function solution(maps) { let xLength = maps[0].length; let yLength = maps.length; let xGoal = xLength-1; let yGoal = yLength-1; let queue = []; // queue의 초기값으로 y, x 값과 (0, 0)은 방문했기 때문에 리턴할 answer은 1로 둔다 queue.push([0, 0, 1]); while(queue.length) { // queue에 있는 요소 꺼내기 let [y, x, answer] = queue.shift(); // x값이 0보다 작거나 xLength보다 길다면 즉, maps에 없는 좌표면 while문 조건식으로 이동 if(x < 0 || x >= xLength) continue; // y값이 0보다 작거나 yLength보다 길다면 즉, maps에 없는 좌표면 while문 조건식으로 이동 if(y < 0 || y >= yLength) continue; // maps[y][x]값이 0이라면 즉, 갈 수 없는 길이라면 while문 조건식으로 이동 if(maps[y][x] === 0) continue; // x와 y값이 상대팀 진영에 도착했다면 answer 리턴 if(x === xGoal && y === yGoal) { return answer; } // 방문한 좌표 0으로 바꿈 maps[y][x] = 0; // queue에 현재 좌표의 상하좌우 각각의 좌표와 answer+1 푸쉬 queue.push([y+1, x, answer+1]); queue.push([y, x+1, answer+1]); queue.push([y-1, x, answer+1]); queue.push([y, x-1, answer+1]); } // while문이 끝났다면 갈 곳이 없다는 의미이므로 -1 리턴 return -1; }
'Algorithm' 카테고리의 다른 글
프로그래머스 - 하노이 탑 (0) 2023.06.07 프로그래머스 - 구명보트 (0) 2023.06.07 프로그래머스 - 바탕화면 정리 (0) 2023.05.26 프로그래머스 - 폰켓몬 (0) 2023.05.25 프로그래머스 - 성격 유형 검사하기 (0) 2023.05.23