[알고리즘] 2023 Kakao Blind 미로 탈출 명령어 (Java)

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

프로그래머스

 

이번 문제는 lv3에 배정된 문제로, 개인적으로는 택배배달 문제보다는 쉽게 풀었다. (택배 배달 문제는 아이디어 내기가 너무 어려웠다)

 

정확히 거리 k만큼 이동하여 미로를 탈출하고, 해당 경로 문자열 중 사전 순으로 가장 빠른 경로를 선택해야하는 문제였다.

 

약간 변형된 그래프 탐색 문제로, 특정 거리 k에 맞춰 탐색해야 했기 때문에 bfs보다는 dfs가 이 문제에 더 적합하여 dfs를 사용했다.

 

방향에 따라 경로 알파벳이 각각 l, r, u, d로 할당되어있고 해당 경로 중 사전 상으로 가장 빠른 문자열을 출력해야 하므로

 

dfs 탐색 순서를 문자열 순서인 d, l, r, u 순서대로 진행하고 해당되는 경로가 있는 경우 탐색을 종료하는 식으로 구현했다.

 

그 다음으로 문제에서 나온 미로를 탈출할 수 없는 경우 "impossible"을 출력한다는 조건에 맞추기 위해

 

impossible이 발생하는 조건 몇 가지를 구별했다.

 

1. 입력받은 거리 값과 이동해야하는 거리 k의 차이가 홀수인 경우

 

이 문제의 조건 중에서 (x,y)와 (r,c) 격자를 포함해 같은 격자를 두 번 이상 방문해도 된다는 조건이 있었기 때문에,

 

한 지점을 왔다갔다하는 2번의 이동이 가능해진다. 하지만 입력받은 거리 값과 이동해야하는 거리 k의 차이가 홀수 인경우,

 

왕복 이동이 불가능해지기 때문에 절대 도달할 수 없어 impossible 상태가 된다.

 

2. 현재까지 이동한 거리와 ( 현재 지점 - 도착 지점 간의 거리 차이 )를 합한 값이 k와 다른 경우

 

1번 조건은 dfs를 탐색하기 전부터 필터링이 가능한 impossible 케이스였다면, 이 경우는 dfs 탐색을 하면서 중간에 발견할 수 있는 경우이다.

 

이 조건의 경우 문제의 조건 자체를 맞추기 위해 필요한 조건은 아니지만, 해당 조건없이 제출할 경우 몇몇 케이스에서 시간 초과가 발생해

 

불필요한 탐색을 제거해 시간 초과를 회피하기 위해 추가했다. 해당 조건을 통해 필터링되는 경우로는

 

초기 dfs 탐색을 시작하기 전 이동 거리 상으로는 충분히 도달할 수 있었지만, 불필요한 왕복 또는 우회해서 이동하는 등의 과정으로 인해

 

남은 이동 기회 내로는 도착지점에 도착할 수 없는 경우를 걸러내기 위해 사용했다.

 

 

 

class Solution {
    static int dx[] = {1, 0, 0, -1};
    static int dy[] = {0, -1, 1, 0};
    static String dir[] = {"d", "l", "r", "u"};
    static int srcX, srcY, destX, destY, sizeN, sizeM, depthK;
    static int maze[][];
    static String ans;
    
    public void dfs(int x, int y, int depth, String output){
        int idx;
        
        if(!ans.equals("")){
            return;
        }
        
        if(calDis(x, y, destX, destY) + depth != depthK){
            return;
        }
        
        if(depth == depthK){
            if(x == destX && y == destY && ans.equals("")){
                ans = output;
            }
            return;
        }
        
        for(idx = 0; idx < 4; idx++){
            int nextX = x + dx[idx];
            int nextY = y + dy[idx];
            
            if(isValid(nextX, nextY)){
                String nextOutput = output + dir[idx];
                dfs(nextX, nextY, depth + 1, nextOutput);
            }
        }
    }
    
    public int calDis(int x1,int y1,int x2,int y2){
        return Math.abs(x2 - x1) + Math.abs(y2 - y1);
    }
    
    public boolean isValid(int x,int y){
        if(x >= 1 && x <= sizeN && y >= 1 && y <= sizeM){
            return true;
        }
        return false;
    }
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        
        if(Math.abs(calDis(x, y, r, c) - k) % 2 != 0){
            answer = "impossible";
            return answer;
        }
        
        maze = new int[n + 1][m + 1];
        
        srcX = x;
        srcY = y;
        destX = r;
        destY = c;
        sizeN = n;
        sizeM = m;
        depthK = k;
        
        ans = "";
        dfs(srcX, srcY, 0, "");
        
        if(ans.equals("")){
            ans = "impossible";
        }
        
        return ans;
    }
}