[프로그래머스] 미로 탈출 명령어(Java)

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

프로그래머스

미로 탈출 명령어 문제

미로를 탈출했을 때 사전적으로 앞서는 명령어를 찾는 문제

 

#사용 알고리즘

백트래킹(BackTracking)

 

📌문제 접근 포인트

1. 시작하기 전에 불가능한 케이스에 대해서 생각해보자. K는 이동할 수 있는 횟수고, 시작점부터 도착점까지 맨해튼 거리 상(l)으로 K보다 작다면 일단 도착할 수 없는 케이스이다. 또한, 시작점에서 도착점까지 최소한 이동해야하는 l을 이동 횟수에서 차감 했을 때의 값이 홀수이면 도착점에 도착할 수 없다. (도착점과 다르게 이동하면 돌아오는 횟수도 필요하니 짝수만큼 횟수가 남아야한다.)

1-1 최초 시작시 불가능한 경우를 제외해주지 않을 경우 시간 복잡도가 증가해 최대 4**(K)만큼 탐색한다. 가능한 경우만 탐색할 경우 모든 케이스를 탐색하는게 아니므로 굉장히 시간이 줄어들게 된다.

2. 탐색을 진행해보자. 문자 s에 계속해서 하나씩 덧붙여가는 형태로 진행을 한다. 이때, 현재 깊이에서 거리 l까지 더한 값이 K보다 크면 안되고, 결과 값인 text보다 문자 s의 사전적 위치가 뒤처지면 안된다. 

3. 위 조건에 맞게 백트래킹을 구성하되, 탐색을 최소화하려면 사전적으로 앞서는 순서로 찾아야하므로 d -> l -> r -> u 방향 순으로 탐색하도록 방향 순서를 구성해줘야한다. 방향 순서를 지키지 않으면 탐색 횟수가 최악의 경우 4배까지도 늘어날 수 있다.

반응형

⚙ 내가 푼 정답 코드

class Solution {
    public static int N,M,R,C,K;
    public static int[] dy = {1,0,0,-1};
    public static int[] dx = {0,-1,1,0};
    public static String[] move = {"d","l","r","u"}; // 사전적으로 d -> l -> r -> u 순으로 탐색
    public static String text = "z"; // r,l,d,u보다 z는 사전적으로 뒤
    
    public static int distance(int y, int x){ // 현재 위치와 목표까지 거리
        return Math.abs(R - y) + Math.abs(C - x);
    }
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        N = n;
        M = m;
        R = r-1;
        C = c-1;
        K = k;
        // 도착까지 거리보다 K가 작거나, 최소 이동횟수를 제외한 나머지 횟수가 홀수면 불가능
        if (distance(y-1,x-1) > K || (K - distance(y-1,x-1)) % 2 == 1){
            return "impossible";
        }
        find(x-1, y-1, 0, "");
        return text;
    }
    
    public static void find(int a, int b, int d, String s){
        // 현재 위치에서 목표까지 거리보다 짧거나 결과 값보다 사전적으로 뒤처지면 돌아가기
        if(d + distance(a, b) > K || s.compareTo(text) > 0){
            return;
        }
        
        // K를 다썼는데 E에 도착했다면 저장
        if (d == K && a == R && b == C){
            text = s;
            return;
        }
        
        // 범위 값에서 벗어나지 않게 백트래킹 구성
        for(int i = 0; i< 4; i++){
            int ny = a + dy[i];
            int nx = b + dx[i];
            if(0 <= ny && ny < N && 0 <= nx && nx < M){
                find(ny, nx, d+1, s + move[i]);
            }
        }
    }
}