문제

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

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

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

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

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

lldud
ulldd
rdlll
dllrl
dllud
...
이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

제한 사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

풀이

시간 초과

• 보자마자 BFS를 사용하여 풀어야 겠다고 생각했다.
• 여느 BFS 문제와 동일하게 dx, dy 방향 정해서 for문 안에서 재귀 돌려주고, 탈출조건 만족되면 탈출하는 식으로 작성했었다. → 시간 초과...

아이디어

• 일단 이 문제에서 '사전 순으로' 답을 원한다는 것을 알기 때문에, 우리는 반복을 돌리더라도 사전순으로 d, l, r, u 순으로 돌려야 한다.
• 쓸 데 없는 반복을 방지하기 위해, 미리 impossible한 경우를 정의하여 함수 상단에서 return 해준다.
  • 각 좌표(x, y), (r, c) 사이의 맨해튼 거리를 쟀을 때 이미 k를 넘어가는 경우
  • (문제를 풀다보면 깨닫게 되겠지만) 각 좌표 사이의 맨해튼 거리와 k의 차가 2의 배수가 아닌 경우
• BFS 말고 DFS로 푼다. DFS는 남은 맨해튼 거리와 k가 같아질 때까지 실행한다.
  • 그래야 사전순으로 가장 빠른 문자열의 탈출경로를 얻을 수 있다.
  • DFS를 실행할 때 마찬가지로 사전순으로 유리하게 d, l, r, u 순으로 돌려야 한다. (물론 갈 수 있는 방향인지 확인하면서)
• 남은 맨해튼 거리와 k가 같아졌다면 또 사전순으로 유리하게 d, l, r, u 순으로 남은 k를 소진하며 이동한다. 남은거리가 k와 같으므로 무조건 정직하게(예외 케이스 생각할 필요 없이) 사전순으로 나열하면 된다.

코드

function getDist(x, y, r, c) {
    return Math.abs(x - r) + Math.abs(y - c);
}

function getDirection(n, m, x, y) {
    let dRow = [1, 0, 0, -1];
    let dCol = [0, -1, 1, 0];
    
    // 사전순으로 가장 먼저 걸리는 방향을 반환한다.
    for(let i=0; i<4; i++) {
        const newRow = x + dRow[i],
              newCol = y + dCol[i];
        if(newRow > 0 && newRow <= n && newCol > 0 && newCol <= m) return i;
    }
}

function solution(n, m, x, y, r, c, k) {
    let answer = ''
    let dist = getDist(x, y, r, c);
    let standard = k - dist;
    if (standard < 0 || standard % 2 != 0) return "impossible";
    
    let cmd = ['d', 'l', 'r', 'u'];
    
    //좌표를 계속 이동시키면서, 남은 거리도 업데이트 쳐준다.
    //두 점 사이의 거리와 k가 같아질 때까지 한다.
    while(dist < k) {
        let direction = getDirection(n, m, x, y);
        answer += cmd[direction];
        
        if(direction === 0) x++;
        if(direction === 1) y--;
        if(direction === 2) y++;
        if(direction === 3) x--;
        k--;
        dist = getDist(x, y, r, c);
    }
    
    //이제 남은 거리와 k가 같으니 무조건 순서대로 들어가면 된다.
    if(x < r) answer += 'd'.repeat(r-x);
    if(y > c) answer += 'l'.repeat(y-c);
    if(y < c) answer += 'r'.repeat(c-y);
    if(x > r) answer += 'u'.repeat(x-r);
    
    return answer;
    
}