미로 탈출 명령어

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

프로그래머스

주어진 맵에서 시작 지점과 도착 지점이 주어진 상태로 k 거리로 도달 가능한 경로를 찾는 문제입니다.

최단 거리가 아닌 k 거리의 위치를 찾아야 하고, 도달 가능한 경로 중에서 알파벳 정렬이 가장 빠른 조건이 붙기 때문에 몇 가지 예외 처리가 필요합니다.

 

우선, dfs 와 같은 탐색을 통하면 k ( 입력 최대 값 ) 이 크기 때문에 시간이 오래 걸릴 수 있습니다.

그것과는 별개로 문제와 주어진 조건을 생각하면 굳이 경로 검색을 하지 않더라도 문제를 해결할 수 있습니다.

 

예를 들어 주어진 맵에서는 장애물이 없기 때문에 시작 지점과 도착 지점의 차이 ( delta ) 만으로 최단 경로를 찾을 수 있습니다.

여기서 문제는 k 이동 거리를 만족해야 하고, 알파벳 정렬을 만족하기 위해서 이동 수단 ( 상, 하, 좌, 우 ) 에서 d, l, r, u 가 먼저 올 수 있도록 해야 합니다.

 

1. k 와 최단 거리가 같다면 문제가 없고, k 가 큰 경우는 무의미한 반복 이동이 추가되어야 합니다.

2. 무의미한 반복 이동은 l, r ( pair ) 또는 d, u ( pair ) 가 쓰일 수 있는데 d 가 l 보다 알파벳이 먼저 오기 때문에 d 이동이 가능한 경우를 먼저 반영해야 합니다.

 

맵에서 down 이 가능한 경우는 도착 지점에 도착하고 n 이 도달하지 않은 경우가 있고 - ( 1 )

이런 round 이동을 반영하고도 k 값이 남는 다면 left ( 여기서는 1 ) 이 가능한 경우까지 이동 합니다 - ( 2 )

 

그런 다음에는 u, d 또는 r, l 이 필요한데 이 중에 r, l 이 알파벳 순서가 빠르므로 r, l 로 채우면 됩니다.

 

function solution(n, m, x, y, r, c, k) {
    var dx = r - x;
    var dy = c - y;

    var diff = Math.abs(dx) + Math.abs(dy);

    // fail cases
    // case 1 : unreachable distance
    // case 2 : can't reach that 'k' size
    if (diff > k
        || (k - diff) % 2 == 1) {
        return 'impossible';
    }

    var direction = { d: 0, l: 0, r: 0, u: 0 };

    direction[dx > 0 ? 'd' : 'u'] = Math.abs(dx);
    direction[dy > 0 ? 'r' : 'l'] = Math.abs(dy);

    var roundMoveCount = (k - diff) / 2;

    var answer = '';

    answer += 'd'.repeat(direction['d']);

    var roundOfDown = Math.min(roundMoveCount, n - (x + direction['d']));
    answer += 'd'.repeat(roundOfDown);
    direction['u'] += roundOfDown;

    roundMoveCount -= roundOfDown;

    answer += 'l'.repeat(direction['l']);

    var roundOfLeft = Math.min(roundMoveCount, y - direction['l'] - 1);
    answer += 'l'.repeat(roundOfLeft);
    direction['r'] += roundOfLeft;

    roundMoveCount -= roundOfLeft;

    answer += 'rl'.repeat(roundMoveCount);
    answer += 'r'.repeat(direction['r']);
    answer += 'u'.repeat(direction['u']);
    
    return answer
}