[Lv.3] 미로 탈출 명령어 - JAVA

class Solution {
    static int endX,endY;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";

        //d -> l -> r -> u
       
        int height=Math.abs(r-x);
        int width=Math.abs(c-y);
        int sum=height+width;
        if(sum%2==1&&k%2!=1)
            return "impossible";
        if(sum%2==0&&k%2!=0)
            return "impossible";
        if(sum>k)
            return "impossible";
        //빠른순으로 이동을 시도하고 되면 해당 경로로만 가는거 약간 그리디 느낌으로 해야될 듯
        int left=k;
        int nowX=x;
        int nowY=y;
        endX=r;
        endY=c;
        while(k!=0){
            if(nowX<n){
                //d
                if(getDis(nowX+1,nowY)<=k-1){
                    answer+="d";
                    nowX++;
                    k--;
                    continue;
                }

            }
            if(nowY>1){
                //l
                if(getDis(nowX,nowY-1)<=k-1){
                    answer+="l";
                    nowY--;
                    k--;
                    continue;
                }
            }
            if(nowY<m){
                //r
                if(getDis(nowX,nowY+1)<=k-1){
                    answer+="r";
                    nowY++;
                    k--;
                    continue;
                }
            }
            if(nowX>1){
                //u
                if(getDis(nowX-1,nowY)<=k-1){
                    answer+="u";
                    nowX--;
                    k--;
                    continue;
                }
            }
            System.out.println("Error.. this should never show up");
        }

        return answer;
    }
    public int getDis(int x,int y){
        int abs = Math.abs(Math.abs(Math.abs(endX - x) + Math.abs(endY - y)));
        return abs;
    }

    //13,21
}

---

처음엔 DFS로 풀어서 제출했으나 당연하게도 시간초과가 났다. 이 문제는 갔던 경로를 다시 돌아갈 수 있고 이 과정에서 반복횟수가 상당히 늘어나기에 시간초과가 날 수 밖에 없다. 그래서, 목적지까지 가는 최대의 경로 (즉, 알파벳 순이 빠른 경로) + 출발지로 돌아오는 최대의 경로 이런식으로 풀어보려 했는데 생각해보면 출발지로 돌아오지 않아도 최대의 경로를 가질 수 있다.

즉, 문제의 예시에서 처럼 dllrl의 경우 출발지로 돌아오지 않지만 최대의 경로가 될 수 있다.

 

그래서, 다시 생각을 해보았는데 최대의 경로는 그때그때마다 갈 수 있는 경로 중 가장 알파벳 순번이 빠른 경로를 택하는 경우다.

즉, d l r u 순으로 알파벳이 나열되니 항상 내려갈 수 있으면 내려가야 하고 그렇지 않다면 왼쪽으로 움직이는게 전체 경우의 수에서 가장 빠른 경로이다.

따라서, 이 문제는 그리디 알고리즘으로 쉽게 풀어낼 수 있다.

 

코드와 로직 자체가 단순하여 추가적으로 설명을 더 하긴 뭐 하지만,

맨 위의 impossible판단하는 부분을 설명해보자면

우리가 5번 움직일 수 있는데 출발지부터 목적지까지의 거리가 7칸이라면 경로가 존재할 수 밖에 없다. (목적지까지 5번이동 거기서 rl, ud ..)

그러나, 만약 6칸이라면 출발지부터 목적지까지 갈 수 있는 경로는 존재할 수 없다 (목적지까지 5번이동 거기서 추가로 1번이동 -> 목적지 기준 lrud는 가능하지만 목적지에 정확히 도착할 수 없다.)

k가 짝수인 경우도 마찬가지 이므로, k와 목적지까지의 거리가 (짝수,짝수) or (홀수,홀수)가 아니라면 해당 case는 불가능한 case가 되기에 바로 impossible을 리턴하여 준다.

그 외의 경우 중 불가능한 경우는 목적지까지 거리보다 이동 칸수가 적은 경우뿐이다.

 

따라서, 해당 경우의 경우 바로 impossible을 리턴하고 나머지의 경우 그리디 탐색을 통해 최적의 경로를 찾아 리턴한다.