[DFS/백트래킹] - LV3 - 2023 KAKAO BLIND RECRUITMENT - 미로 탈출 명령어

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

프로그래머스

🌿 - 문제 설명

📌- 풀이

문제를 보고 처음에는 BFS로 {d, l , r , u} 의 순서대로 완전탐색을 하면 되겠구나 생각해서 그렇게 문제를 풀려고 했는데, 전부 다 탐색을 하게 되면 분명 시간 초과가 날 것 같다고 생각해서 다른 방식을 생각해보게 되었다.

 

일단 주어진 문제에서 문자열을 사전순서대로 가장 빠른 순이라고 했기 때문에 dlru순으로 탐색을 하긴 하는데, 이것을 DFS로 탐색을 하게되면 K의 수 만큼 -> 예를들어 k가 5라면

 

ddddd부터 시작해서 ddddl -> ddddr -> 이렇게 탐색하게 되고 가장 먼저 k == 0 이고 목적지에 도착한 문자열이 정답이 되기 때문에 그렇게 구현을 했다. 처음 풀었을 때 시간 초과가 났고, 어떻게 가지치기를 해야할지 고민을 해서 개선을 했다.

 

🔥 - 처음 시간 초과 난 코드

class Solution {
        static int[] dx = {1,0,0,-1};
        static int[] dy = {0,-1,1,0};
        static String[] direction = {"d","l","r","u"};
        static String result ="";
        static int N,M;
        static boolean fin = false;
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        N = n;
        M = m;
        
        
        dfs(x-1,y-1,r-1,c-1, k, "");
        answer = result.equals("") ? "impossible" : result;
        
        
        return answer;
    }
    
    public void dfs(int startX, int startY,int endX,int endY, int k , String str){
        if(k==0 && startX == endX && startY == endY){
            result = str;
            fin = true;
            return;
        }
        
        if(k==0 || fin){
            return;
        }
        for(int i =0;i<4;i++){
            int nx = startX + dx[i];
            int ny = startY + dy[i];
            if(0<= nx && nx<N && 0<= ny && ny<M){
                dfs(nx,ny,endX,endY, k-1, str+direction[i]);
            }
        }
        
    }
}

 

 

위의 방식대로 하면 정답이 나오지 않더라도 탐색을 하는 경우가 많기 때문에

아래처럼 현재 위치한 곳과 도착지점의 거리를 구해서 해당 수가 k와 짝수인지 홀수인지 비교해서 짝/홀수가 같다면 탐색할 수 있고, 짝 홀수가 다르다면 갈 수 없는 곳이라 탐색할 필요가 없기 때문에 해당 조건으로 가지치기를 해서 시간초과를 해결했다.

 

🔥 - 개선한 코드

class Solution {
        static int[] dx = {1,0,0,-1};
        static int[] dy = {0,-1,1,0};
        static String[] direction = {"d","l","r","u"};
        static String result ="";
        static int N,M;
        static boolean fin = false;
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        N = n;
        M = m;
        
        int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
        dfs(x-1,y-1,r-1,c-1, k, "",diff);
        answer = result.equals("") ? "impossible" : result;
        
        
        return answer;
    }
    
    public void dfs(int startX, int startY,int endX,int endY, int k , String str, int diff){
        if(k==0 && startX == endX && startY == endY){
            result = str;
            fin = true;
            return;
        }
        
        if(k==0 || fin){
            return;
        }
        for(int i =0;i<4;i++){
            int nx = startX + dx[i];
            int ny = startY + dy[i];
            if(0<= nx && nx<N && 0<= ny && ny<M && diff <=k){
                if((diff % 2 == 0 && k % 2 == 0) || (diff %2 == 1 && k %2 == 1)){
                dfs(nx,ny,endX,endY, k-1, str+direction[i],Math.abs(nx-endX) + Math.abs(ny-endY));
                }
            }
        }
        
    }
}