[JavaScript] 프로그래머스: 미로 탈출 명령어

난이도 : Level 3
알고리즘 유형 : 그리드 알고리즘
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

 

 

문제

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발하여 (r, c)로 이동해서 탈출해야 합니다.
단, 미로를 탈출하는 조건이 세 가지 있습니다.

• 격자의 바깥으로는 나갈 수 없습니다.
• (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다.
  이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
• 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야합니다.
  이동 경로는 상, 하, 좌, 우로 이동시, 'u', 'd', 'l', 'r'로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

입력

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다.

출력

이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 
단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

 

 

문제 풀이

• 출발 지점에서 탈출 지점까지의 거리가 이동할 수 있는 거리 k 보다 작다면 탈출할 수 없다.
• 이동할 수 있는 거리 k에서 탈출까지의 거리를 뺐을 때 2로 나누어 떨어지지 않으면 탈출할 수 없다.
• k가 탈출할 수 있도록 주어지고 k가 충분히 크다고 생각해보자!
  • 탈출한 경로가 문자열 순으로 가장 빠르기 위해서는 d > l > r > u 순으로 문자열이 나와야한다.
    따라서 탈출한 경로는 'dddllll~~~' 이렇게 되어야 한다.
  • d가 가장 많기 위해서, 아래쪽 경계에 걸리기 전까지 d로 채울 수 있다.
  • l이 가장 많기 위해서, 왼쪽 경계에 걸리기 전까지 l로 채울 수 있다.
  • 위 두가지를 진행하고 나면 노드는 (N, 1) 에 존재하므로 앞으로는 rl로 k 거리까지 채우면 된다.
    ( rl이 ud 보다 사전순으로 빠름.)

 

코드

function solution(N, M, si, sj, ei, ej, k) {
    let [d, l, r, u] = [ei - si, sj - ej, ej - sj, si - ei].map((v) => Math.max(v, 0));
    const distance = d + l + r + u;
    
    const diff = k - distance;
    if ( diff < 0 || diff % 2 !== 0 ) return "impossible";
    
    const vertical = Math.min(diff / 2, N - si - d);
    d += vertical;
    u += vertical;
    const horizontal = Math.min(diff / 2 - vertical, sj - l - 1);
    l += horizontal;
    r += horizontal;
    const extra = diff / 2 - vertical - horizontal;
    
    let answer = '';
    answer += d ? 'd'.repeat(d) : '';
    answer += l ? 'l'.repeat(l) : '';
    answer += extra ? 'rl'.repeat(extra) : '';
    answer += r ? 'r'.repeat(r) : '';
    answer += u ? 'u'.repeat(u) : '';
    
    return answer;
}

 

 

회고

만약에 입력이 map으로 이차원 인접 배열로 주어졌다면 지금처럼 map의 index 기반인 숫자로 풀 생각을 하지 못하고, dfs로 풀생각을 했을 것 같다. 그리고 그렇게 풀었다면 코드의 양도 더 길어지고, 실행 시간도 훨씬 더 많이 들었을 것이다.
하지만 오늘 숫자로 풀어봄으로써 이와 비슷하지만 map으로 주어지는 문제를 만났을 때, 빠른 시간 내에 풀 수 있을 것이라고 생각한다.