문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.
제한사항
5 ≤ maps의 길이 ≤ 100
5 ≤ maps[i]의 길이 ≤ 100
maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
S : 시작 지점
E : 출구
L : 레버
O : 통로
X : 벽
시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.
입출력 예
maps result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"] 16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"] -1풀이
- 먼저 시작 지점, 레버 지점, 도착 지점을 각각 구한다.
- 시작 지점에서 레버 지점으로 가는 과정
- 두 지점의 x 좌표 차이가 0보다 크고 이동 지점이 X가 아닌 경우 해당 위치로 이동.(x가 0보다 큰/작은 경우, y가 0보다 큰/작은 경우)
- temp가 answer와 같다면 아무 이동도 못한 것이므로 -1을 return한다.
- 그게 아닐 경우 두 좌표가 같아질 때까지 해당 시행을 반복한다.
- 레버 지점에서 도착 지점으로 가는 과정
- 2번 과정과 동일.
=> 무조건 해당 방향으로만 이동하려고 해서 제대로 풀리지 않았다.
ex. [0,4] -> [3,4] 로 이동해야 하는데 [2,4]에 벽이 있는 경우 아래로 갈 수 없고 우회해서 가야 하는데 아래로만 가려고 하니까 -1이 출력됨.
function solution(maps) {
let answer = 0;
let temp = 0;
let s = maps.map((el,i) => el.includes("S") ? [i,el.indexOf("S")] : '').filter(el => el !== "").flat(); // 시작 지점
let l = maps.map((el,i) => el.includes("L") ? [i,el.indexOf("L")] : '').filter(el => el !== "").flat(); // 레버 지점
let e = maps.map((el,i) => el.includes("E") ? [i,el.indexOf("E")] : '').filter(el => el !== "").flat(); // 종료 지점
// 시작 -> 레버
while(s[0] !== l[0] || s[1] !== l[1]){
let x = l[0] - s[0];
let y = l[1] - s[1];
if(x > 0){
if(maps[s[0]+1][s[1]] !== "X"){
temp = answer + 1;
x--;
s[0] = s[0] + 1;
}
}else if(x < 0){
if(maps[s[0]-1][s[1]] !== "X"){
temp = answer + 1;
x--;
s[0] = s[0] - 1;
}
}
if(y > 0){
if(maps[s[0]][s[1]+1] !== "X"){
s[1] = s[1] + 1;
temp = answer + 1;
y--;
}
}else if(y < 0){
if(maps[s[0]][s[1]-1] !== "X"){
s[1] = s[1] - 1;
temp = answer + 1;
y--;
}
}
if(temp === answer){
return -1;
}else{
answer = temp;
}
}
// 레버 -> 종료
while(l[0] !== e[0] || l[1] !== e[1]){
let z = e[0] - l[0];
let m = e[1] - l[1];
if(z > 0){
if(maps[l[0]+1][l[1]] !== "X"){
temp = answer + 1;
z--;
l[0] = l[0] + 1;
}
}else if(z < 0){
if(maps[l[0]-1][l[1]] !== "X"){
temp = answer + 1;
z--;
l[0] = l[0] - 1;
}
}
if(m > 0){
if(maps[l[0]][l[1]+1] !== "X"){
l[1] = l[1] + 1;
temp = answer + 1;
m--;
}
}else if(m < 0){
if(maps[l[0]][l[1]-1] !== "X"){
l[1] = l[1] - 1;
temp = answer + 1;
m--;
}
}
if(temp === answer){
return -1;
}else{
answer = temp;
}
}
return answer;
}다른 풀이 - BFS를 이용한 풀이
- 시작 위치와 레버 위치 구하기
- 시작 -> 레버 까지 소요 시간
- 상하좌우로 이동하여 벽을 만나거나 좌표 범위를 벗어나지 않을 경우 queue에 담는다.(이동할 수 있는 위치는 모두 queue에 담기게 됨.)
- 지나간 위치는 벽으로 표시한다.
- 한 사이클이 지나면 소요 시간을 1 증가시킨다.
- 쭉 이동해서 target을 만나게 되는 경우 소요 시간을 return한다.
- 타겟을 만나지 못한 경우 -1을 return한다.
- 레버 -> 도착 까지 소요 시간
- 둘중 하나라도 못 가면 -1 return, 갈 수 있으면 시간 합해서 return
중요 포인트
- 상하좌우 행렬 좌표를 이용해 상하좌우로
이동한 위치를 모두 체크한다.(BFS)- 벽뿐만 아니라 좌표 값의 범위를 벗어나는지도 체크해야 한다.
- 지나간 위치는 벽으로 표시해 다시 지나가지 못하게끔 한다.(최단거리를 위해)
function solution(maps) {
let start = []; // 스타트 위치
let lever = []; // 레버 위치
/* 1) start-lever, lever-end 두번을 나눠 최단
거리를 구하기 위해 두개의 map을 생성한다. */
const maps2 = maps.map(item => item.split(''));
const maps3 = maps.map(item => item.split(''));
// 2) 반복문을 통해 시작, 레버 위치를 찾는다.
for(let i=0; i<maps.length; i++) {
for(let j=0; j<maps[i].length; j++) {
if(maps[i][j] === "S") start = [i,j];
else if(maps[i][j] === "L") lever = [i,j]
}
}
// 3) start-lever 최단거리 시간
const a = target(start, [...maps2], "L");
// 4) lever-end 최단거리 시간
const b = target(lever, [...maps3], "E");
// 5) 둘중에 하나라도 거쳐가지 못한다면 -1를 반환한다.
if(a === -1 || b === -1) return -1
// 6) 거쳐간다면 최단거리 합을 반환한다.
return a+b;
}
// 7) 최단거리 구하는 함수
function target(start, arr, target) {
let time = 0; // 걸리는 시간
const dx = [-1, 1, 0, 0]; // 상하좌우 행열 좌표
const dy = [0, 0, -1, 1];
const q = [start];
const n = arr.length; // 좌표 값의 범위를 제한하는 n, m
const m = arr[0].length;
arr[start[0]][start[1]] = 'X'; // 시작 위치를 막기
// 8) 너비탐색(BFS)
while(q.length > 0) {
// 9) q의 길이가 변하면 안되기 때문에 변수로 선언한다.
// 한 사이클(이동가능 좌표들)의 횟수가 push로 변하기 때문에 값 고정
let size = q.length;
for(let i=0; i<size; i++) {
const [x, y] = q.shift();
// 10) 상하좌우 반복
for(let j=0; j<4; j++) {
let nx = x + dx[j];
let ny = y + dy[j];
// 11) 좌표 값 범위에 있으면서 벽(X)이 아니라면
if(nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] !== 'X') {
// 12) target이랑 만나게 되면 걸리는 시간을 반환한다.
if(arr[nx][ny] === target) {
return time+1;
}
// 13) 현재 좌표를 q에 넣고 다시 갈 수 없게 벽으로 막는다.
q.push([nx, ny]);
arr[nx][ny] = 'X';
}
}
}
// 14) 한 사이클이 끝나면 1초 증가
time++;
}
// 15) target을 만나지 못한다면 -1 반환
return -1;
}
모든게 새롭고 재밌는 프론트엔드 새싹