[programmers/js] 미로 탈출 명령어

미로 탈출 명령어

https://school.programmers.co.kr/learn/courses/30/lessons/150365

문제 설명

이 문제는 n x m 크기의 미로에서 출발 지점 (x, y)에서 목표 지점 (r, c)로 k만큼 이동하여 탈출하는 경로를 찾는 문제입니다. 이때 이동 경로는 사전 순으로 가장 빠른 경로를 선택해야 하며, 이동은 l(왼쪽), r(오른쪽), u(위쪽), d(아래쪽)로 표시됩니다.

조건에 맞는 경로가 존재하지 않으면 impossible을 반환해야 합니다.

문제 분석

이동 규칙
1. (x, y)에서 (r, c)로 가는 경로가 존재해야 하며, 미로 밖으로 나갈 수 없습니다.
2. 이동 횟수는 정확히 k여야 하며, 이동 경로는 사전 순으로 가장 빠른 경로여야 합니다.
3. 이동은 상, 하, 좌, 우로만 가능하며, 각 이동은 한 칸씩만 진행됩니다.
해결 전략:

• 최단 경로 계산: 출발점에서 목표점까지의 최단 거리를 계산합니다. 이는 dCount, lCount, rCount, uCount로 나타낼 수 있습니다.

• 이동 거리 확인: k가 최단 거리보다 짧거나, k - 최단 거리가 홀수일 경우 이동이 불가능합니다.

• 이동 경로 조정: k가 최단 거리보다 길다면, 여분의 이동을 사전 순으로 처리하여 경로를 결정합니다.

구현

1. 이동 방향을 사전 순서로 d, l, r, u의 순서를 가지도록 합니다.
2. 출발 -> 도착까지 최단 거리로 이동하는 순서를 기록합니다.
3. 추가 이동이 필요한 경우 처리합니다.

impossible Case
1. 최소 이동 거리가 k보다 큰 경우
2. 목적이에 도착 후 추가 이동이 필요한데, 다시 돌아 올 수 없는 경우, (k - 이동거리)가 홀수인 경우

추가 이동의 경우
추가 이동도 d -> l -> r -> u 순서로 이동합니다.

한 가지 생각해야 할 부분은 3번의 이동('ddl')으로 도착 후 이동 거리가 남아 'du'를 추가한다면 ddldu가 아닌 dddlu를 정답으로 반환합니다.

function solution(n, m, x, y, r, c, k) {   
    // 출발점에서 목표점까지의 최소 이동 횟수 계산
    const move = [r - x, y - c, c - y, x - r].map((v) => Math.max(0, v));
    let [dCount, lCount, rCount, uCount] = move;  // d, l, r, u 이동 횟수
    const moveSum = move.reduce((a, b) => a + b);  // 최소 이동 거리
    const diff = k - moveSum;  // 추가 이동 거리

    // 이동할 수 없거나 k가 홀수인 경우 "impossible"
    if (diff < 0 || diff % 2 === 1) return "impossible";

    // 이동 경로 조정
    const vMove = Math.min(diff / 2, n - x - dCount);
    dCount += vMove;
    uCount += vMove;
    const hMove = diff / 2 - vMove;
    lCount += hMove;
    rCount += hMove;

    // 이동 경로 생성
    let answer = dCount ? "d".repeat(dCount) : "";  // d 이동
    let hStart = y;

    // 왼쪽 이동 처리
    while (lCount > 0) {
        if (hStart > 1) {
            hStart--;
            answer += "l";
        } else {
            answer += "rl";
            rCount--;
        }
        lCount--;
    }

    // 오른쪽 이동 처리
    answer += rCount ? "r".repeat(rCount) : "";
    // 위쪽 이동 처리
    answer += uCount ? "u".repeat(uCount) : "";

    return answer;
}