[Programmers] 미로 탈출 명령 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150365#

프로그래머스

문제 풀이

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요.

 

전체를 탐색하면 무조건 시간초과 or 메모리 초과가 발생할 것이라고 생각했기 때문에 최적의 방법을 계속 생각했습니다. 우선, 문자열 기준으로 사전순으로 가장 앞에 오는 것만 출력하면 되기 때문에 나머지는 굳이 탐색하지 않아도 됩니다. 그래서 4방향 탐색할 때 문자열 기준으로 d, l, r, u순으로 dx,dy를 설정하여 차례대로 이동한 방향에서 도착할 수 있다면 나머지 방향은 탐색하지 않도록 break를 걸었습니다.

또한, 현재 방향에서 도착지점까지 거리가 가능한지 판별하여 불필요한 탐색을 줄일 수 있었습니다.

코드

import java.util.*;
class Solution {
    
    int DIR = 4;
    int N = 0;
    int M = 0;
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, -1, 1, 0};    
    Map<Integer, String> map = new HashMap<>();
    String answer = "";
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {                
        
        // 불가능
        int diffX = Math.abs(x-r);
        int diffY = Math.abs(y-c);
        if(diffX + diffY > k || (diffX+diffY) % 2 != k % 2) return "impossible";
        
        // init
        N = n;
        M = m;
        map.put(0, "d");
        map.put(1, "l");
        map.put(2, "r");
        map.put(3, "u");
        
        // dfs
        dfs(new StringBuilder(), 0, k, x, y, r, c);
        
        return answer;
    }
    
    
    public boolean dfs(StringBuilder sb, int depth, int k, int x, int y, int r, int c) {
        if(!check(x, y, r, c, k, depth)) return false;
            
        if(depth == k) {                 
            if(x == r && y == c) answer = sb.toString();
            return false;
        }
              
        for(int dir=0; dir<DIR; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(!isRange(nx, ny)) continue;
            sb.append(map.get(dir));
            if(dfs(sb, depth+1, k, nx, ny, r, c)) break;
            sb.deleteCharAt(sb.length() - 1);
        }           
        
        return true;
    }
    
    public boolean check(int x, int y, int r, int c, int k, int depth) {
        int diffX = Math.abs(x - r);
        int diffY = Math.abs(y - c);        
        if(diffX + diffY > k - depth) return false;  
        return true;
    }
    
    public boolean isRange(int x, int y) {
        return x>0 && y>0 && x<=N && y<=M;
    }
}