[JAVA] 프로그래머스 LEVEL3 미로 탈출 명령어

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

프로그래머스

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT > 미로 탈출 명령어

 

문제 분석

난이도: LEVEL3

문제 설명 

문제의 핵심은 명렁어가 사전 순으로 가장 빠른 경로로 탈출해야 한다. 

 

미로를 탈출할 수 없는 경우 "impossible"을 return

 

명렁어는 총 4개 

l: 왼쪽으로 한 칸 이동
r: 오른쪽으로 한 칸 이동
u: 위쪽으로 한 칸 이동
d: 아래쪽으로 한 칸 이동

 

사전 순서 d / l / r / u 

 

(x, y)에서 (r, c)까지 이동하는 거리가 총 k 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문가능

 

제한사항을 보면 알겠지만 BFS를 사용하면 절대 통과 못하는 문제이다. 

시간 초과 코드(BFS 풀이)

import java.util.*;
class Solution {
    static class Move{
        String data = "";
        int x, y; // x,y 좌표     
        public void add (String input){ // 스트링 빌더에 추가 
            this.data += input;
        }
        public String cur(){
            return data;
        }
        public Move(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int N,M;
    static int [] arx = {-1,1,0,0};
    static int [] ary = {0,0,-1,1};
    static String [] addString = {"u", "d", "l", "r"};
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        x -= 1; y -= 1; r -= 1; c -= 1;
        N = n; M = m;
        String answer = "";
        
        PriorityQueue<Move> q = new PriorityQueue<>((o1,o2) -> {
            for(int i = 0; i < o1.data.length(); i++){
                if(o2.data.length() == i) break;
                if(o1.data.charAt(i) < o2.data.charAt(i)) return -1;
            }
            return o1.data.length() - o2.data.length();
        });
 
        q.add(new Move(x, y)); // 시작 지점 넣어주기 
        while(!q.isEmpty()){   // k >= 1 최소 한번은 이동 
            Move mv = q.poll();
            // System.out.println(mv.x + " " + mv.y + " " + mv.cur() + " " + "answer: " + answer);
            String cur = mv.cur();
          
            // 도착!
            if(cur.length() == k){
                if(mv.x == r && mv.y == c){
                    if(answer.equals("")){
                        answer = cur;
                    }
                    else{
                        for(int i = 0; i < k; i++){
                            if(answer.charAt(i) == cur.charAt(i)) continue;
                            if(answer.charAt(i) > cur.charAt(i)){
                                answer = cur;
                            }
                            break;
                        }
                    }
                }
                continue;
            }
            for (int i = 0; i < 4; i++){
                int nx = arx[i] + mv.x;
                int ny = ary[i] + mv.y;
                if(!validation(nx, ny)) continue;
                Move next = new Move(nx, ny);
                next.data = mv.data + addString[i];
                q.add(next);
            }
        }
        return answer.equals("") ? "impossible" : answer;
    }
    public boolean validation(int nx, int ny){ // 검증기 
        if(0 <= nx && 0 <= ny && nx < N && ny < M) return true;
        return false;
    }
}

 

K의 길이를 보면 알겠지만 BFS를 사용하면 무조건 시간초과가 발생한다. 

 

결과

16.3 / 100 (전부 시간초과)

 

정답 코드 (구현)

class Solution {
    static int N,M;
     // 사전 순서 d l r u  
    static int [] arx = {1,0,0,-1};
    static int [] ary = {0,-1,1,0};
    static String [] ars = {"d", "l", "r", "u"};
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        N = n; M = m;
        if(!possible(n, m, x, y, r, c, k)) return "impossible";
        return make(n, m, x, y, r, c, k);
    }
    public String make(int n, int m, int x, int y, int r, int c, int k){     
        
        x -= 1; y -= 1; r -= 1; c -= 1;
        StringBuilder sb = new StringBuilder();
        
        // 1. ArrayOutOfBounds 테스트
        // 2. 우선순위는 항상 d l r u  
        // 3. 다음 장소 도착 장소 거리 <= k 여야함 
        int cx = x;
        int cy = y;
        while(k > 0){
            for(int i = 0; i < 4; i++){
                int nx = arx[i] + cx;
                int ny = ary[i] + cy;
                if(!validation(nx, ny)) continue;
                int distance = Math.abs(nx - r) + Math.abs(ny - c);
                if(distance <= k - 1){
                   k--;
                   cx = nx; cy = ny;
                   sb.append(ars[i]);
                   break;
                }
            }
        }
        return sb.toString();
        
    }
    // 이동이 가능한지? 
    public static boolean possible(int n, int m, int x, int y, int r, int c, int k){
        int distance = Math.abs(x - r) + Math.abs(y - c);
        
        if(distance > k){ // 이동 불가능 
            return false;
        }
        else if(distance == k){ // 정확한 이동 
            return true;
        }
        else{
            // (k - distance) 짝수면 이동 가능 좌 <-> 우 위 <-> 아래 
            if((k - distance) % 2 == 0) return true;
            return false; 
        }
    }
    public static boolean validation(int nx, int ny){
        if(0 <= nx && 0 <= ny && nx < N && ny < M) return true;
        return false;
    }
}

 

1. 먼저 이동이 가능한지 체크 

 

시작 지점과 도착 지점 좌표를 통해서 필요한 거리를 구한다.

만약 필요한 거리가 K(이동 거리) 보다 크면 탈출 불가능 

필요한 거리 == K 정확한 이동 

필요한 거리 보다 K가 더 크면 2가지 케이스가 발생한다.

 

(K - 필요한 거리) % 2 == 0  

남은 거리를 2라고 예시를 들면 위 아래 좌 우 이렇게 여러가지 방법으로 남은 거리를 (쓸데없이) 사용 가능하다. 

 

(K - 필요한 거리) % 2 == 1

어떤 방식을 사용하든 원하는 좌표로 도착 못한다. 

 

해당 결과를 바탕으로 만약 possible 메서드에서 false 반환을 하면 문제 요구사항에 맞게 "impossible"을 return

 

2. 사전 순으로 가장 빠른 경로 만들기 

 

현재 이동 가능한 좌표 중에 가장 사전 순으로 빠른 명령어로 움직이는 게 핵심이다. 

하지만 2가지 조건을 준다. 

1. ArrayOutOfBounds 격자의 바깥으로는 불가능

2. 사전 순으로 가장 빠른 명령어를 통해서 움직이는 게 중요하지만 만약 도착할 수 없다면 의미가 없다.

(현재 좌표에서 도착 좌표까지의 거리가 남은 이동 횟수보다 먼 경우)

 

2번 조건 예시 

 

현재 좌표는 (2,3) 도착 좌표는 (1,1) 남은 횟수는 3이다. 

가장 우선순위가 높은 명령어는 아래로 가는 명령어(d)인데 사용하면 좌표(3,3)으로 이동한다.

그렇게 이동을 하면 남은 횟수로는 도착 장소에 가지 못한다.

 

그럼 어떻게 이동해야 할까?

 

남은 명령어는 왼쪽 / 오른쪽 / 위 3개 

우선순위 또한 왼쪽 / 오른쪽 / 위 

 

오른쪽 이동은 남은 우선순위도 2위지만 움직이면 격자 바깥으로 움직여서 안된다.

위로 이동하는 것도 가능하지만 우선순위가 왼쪽이 더 높기 때문에 왼쪽으로 이동한다. 

 

그럼 (2,2) 좌표로 아동을 하고 남은 이동 횟수가 2가 된다. 

이런 이동 방식을 머릿속으로 떠올리고 코드로 구현하면 끝이다. 

 

질문은 언제든지 환영입니다!