[JAVA] Programmers 미로 탈출 명령어

풀이 방법

1. PriorityQueue를 사용하여 String이 사전 순으로 계속 정렬되게 한다.
2. 가지치기를 하면서 poll 값을 조사할지 말지 결정한다.
   1. 도착 위치와 현재 위치 거리가 남은 거리보다 크면 절대 도착할 수 없다.
   2. (현재 위치와 도착 위치 사이 거리)와 남은 거리의 홀짝은 같아야 한다.

import java.io.*;
import java.util.*;

class Solution {
    static class load{
        int x;
        int y;
        int time;
        String route;
        load(int x, int y, int time, String route){
            this.x = x; this.y = y; this.time = time; this.route = route;
        }
        public String toString(){
            return route;
        }
    }
    static int[] dx = {1, 0, 0, -1}, dy = {0, -1, 1, 0};
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        PriorityQueue<load> q = new PriorityQueue<>((o1, o2) -> o1.route.compareTo(o2.route));
        q.offer(new load(x-1, y-1, 0, ""));
        boolean[][] v = new boolean[n][m];
        v[x-1][y-1] = true;
        while(!q.isEmpty()){
            load now = q.poll();
            if(now.x == r-1 && now.y == c-1 && now.time == k) return now.route;
            if(now.time > k) continue;
            if(!ispossible(now.x, now.y, r-1, c-1, k-now.time)) continue;
            for(int d=0; d<4; d++){
                int nx = now.x+dx[d];
                int ny = now.y+dy[d];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                String Nroute = "";
                if(d == 0) Nroute = now.route+"d";
                else if(d == 1) Nroute = now.route+"l";
                else if(d == 2) Nroute = now.route+"r";
                else Nroute = now.route+"u";
                q.offer(new load(nx, ny, now.time+1, Nroute));
            }
        }
        return "impossible";
    }
    boolean ispossible(int x, int y, int r, int c, int time){
        int rest = Math.abs(r-x)+Math.abs(c-y);
        if(rest > time) return false;
        if((rest % 2) - (time % 2) == 0) return true;
        return false;
    }
}