프로그래머스 미로 탈출 JavaScript
2023년 2월 16일
문제 풀이
직사각형 격자 형태의 미로에서 최소 시간으로 탈출하는 문제, 출구로 탈출하기 전 레버를 당겨야 출구로 탈출할 수 있다. 그전까지는 출구에 도착해도 탈출할 수 없다.
핵심 아이디어는 시작부터 레버까지의 시간, 레버부터 출구까지의 시간을 BFS로 각각 구하는 것이다.
시작, 출구, 레버의 좌표는 고정이 아니기에 maps를 탐색해 시작 지점, 출구, 레버의 좌표를 저장한 뒤 탐색한다. (start, exit, lever)
탐색을 하는 함수 getTargetLocationTime는 좌표 start에서 좌표 target까지 걸리는 시간을 리턴해주는 함수다. 조건에 만족하는 범위를 탐색하는 동안 target 좌표를 만나면 location을 갱신하고 멈춘다. 탐색하는 동안 못 찾았을 경우는 target까지 갈수 없는 경우이기에 -1을 리턴하고, 찾았을 경우에는 target까지의 걸린 시간을 리턴한다.
시작부터 레버까지, 레버부터 출구까지 각각 시간을 구한 뒤 하나라도 갈 수 없는 경우 -1을 리턴, 이외에는 정상적으로 탈출할 수 있기에 시간을 합쳐서 리턴한다.
solution.js
function solution(maps) {
const X = maps.length;
const Y = maps[0].length;
let start = [0, 0], exit = [0, 0], lever = [0, 0];
const direction = [[-1, 0], [0, 1], [1, 0], [0, -1]];
// 지점 찾기
for (let i = 0; i < X; i++) {
for (let j = 0; j < Y; j++) {
if (maps[i][j] === 'S') {
start = [i, j];
}
else if(maps[i][j] === 'E') {
exit = [i, j];
}
else if(maps[i][j] === 'L') {
lever = [i, j];
}
}
}
// target 좌표까지 걸리는 시간
const getTargetLocationTime = (start, target) => {
const times = new Array(X).fill(0).map(() => new Array(Y).fill(-1));
const stack = [[...start]];
let location = [-1, -1];
times[start[0]][start[1]] = 0;
while (stack.length > 0) {
const [x, y] = stack.shift();
if (x === target[0] && y === target[1]) {
location = [x, y];
break;
}
for (const di of direction) {
const dx = x + di[0];
const dy = y + di[1];
if (0 <= dx && dx < X && 0 <= dy && dy < Y && maps[dx][dy] !== 'X' && times[dx][dy] === -1) {
times[dx][dy] = times[x][y] + 1;
stack.push([dx, dy]);
}
}
}
return location[0] === -1 ? -1 : times[target[0]][target[1]];
};
const leverTime = getTargetLocationTime(start, lever);
const exitTime = getTargetLocationTime(lever, exit);
if (leverTime === -1 || exitTime === -1) {
return -1;
}
return leverTime + exitTime;
}