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

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

프로그래머스

 

역시 사람은 많이 시도할수록 빨리 성장한다.

 

원래는 lv3여서 어렵게 가려고 했다.

왕복 횟수와 최단 거리로 가는 횟수를 구해서 그 두 개가 양수이면 계속 가는 것으로 했다.

그리고 왕복 횟수를 줄일 때 왕복 배열에 기록해서 다시 되돌아오도록 했다.

그러나 너무 복잡해져서 (왕복횟수랑 최단 거리로 가는 횟수를 어떻게 구분? 저 왕복 배열 관리 등 등) 검색했다.

 

답은 간단했다.

그 다음으로 가는 위치 ~ 목표 지점까지의 거리 < 남은 횟수 -> 이동(왕복 포함) 가능! 사전순으로 빠른 곳으로 가!

 

참고) 현재 위치 ~ 목표 지점까지의 거리 = 맨해튼 거리 = | x1 - x2 | + | y1 - y2 |

=> 다음 위치와 목표 지점까지의 맨해튼 거리 <= 이동 횟수 - 1 (아직 이동 안 했으니까)

 

코드는 아래와 같다.

생각해보면 가장 단순한 게 정답이다... 쉽게 생각해보자!

(주석에도 설명이 있다.)

 

/*
어려운 시뮬레이션 냄새가 난다
일단 최단 거리로 이동 + 왕복 (du, lr)
*/

function solution(n, m, x, y, r, c, k) {
    var answer = [];
    
    const dr = [1, 0, 0, -1];
    const dc = [0, -1, 1, 0];
    
    // d -> l -> r -> u 사전 순
    const dir = ['d', 'l', 'r', 'u'];
    
    // 최소 횟수 구하기
    let minD = Math.abs(r - x) + Math.abs(c - y);
    
    // 엣지 케이스: 도착할 수 없다면 impossible 반환
    if (minD > k) return "impossible";
    // k만큼 도착하기 위해서는 왔다 갔다 짝수번만큼 횟수가 는다.
    // 즉 거리 % 2 !== 횟수 % 2 -> 불가능
    else if (minD % 2 !== k % 2) return "impossible";
    
    // 0-index로 변환
    let cr = x - 1;
    let cc = y - 1;
    let cnt = k;
    
    const rEnd = r - 1;
    const cEnd = c - 1;
    
    // 횟수를 기준으로 돌린다.
    while (cnt > 0) {
        let isPossible = false;
        
        // 반복문으로 갈 수 있는 지 확인
        for (let i = 0; i < 4; i++) {
            const nr = cr + dr[i];
            const nc = cc + dc[i];
            
            const nd = Math.abs(nr - rEnd) + Math.abs(nc - cEnd);
            
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            // [수정] 다음 좌표에서의 목표지점 과의 거리 d1, 남은 횟수 cnt1 비교
            // 1) d1 > cnt1 -> 실패
            // 2) d1 === cnt1 -> 최단 거리로만 이동
            // 3) d1 < cnt1 -> 왕복 가능!
            if (nd < cnt) {
                cr = nr;
                cc = nc;
                answer.push(dir[i]);
                isPossible = true;
                break;
            }
        }
        
        if (!isPossible) return "impossible";
        cnt--;
    }
    
    return answer.join("");
}