프로그래머스 (카카오) | LV.3 미로 탈출 명령어 - 구현 문풀 (Java)

⬛ 프로그래머스 (카카오) | LV.3 미로 탈출 명령어 - 구현 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

문제는 S (x,y) → E(r,c) 까지 k칸으로 갈 수 있는 경로 중 사전 순 가장 빠른 경로를 리턴하고 없으면 impossible을 리턴하라고 되어 있다.

가장 처음 풀이로 생각이 들었던 건 문자열의 사전 순인 [d, l, r, u] 방향으로 순으로 모든 경로를 완전 탐색 해야 하나 ? 였지만, 격자 2500 안에서 k가 최대 2500까지 들어오는데 매번 4가지 방향으로 2500개의 칸을 갈 수 있는데 4^2500이 나오기 떄문에 선뜻 시도를 못했다.

나중에 찾아보니 DFS로 잘 구현해놓은 풀이도 꽤 있었고 카카오 해설지에서도 DFS뿐 아니라 다양한 방식으로 해결이 가능하다고 되어 있다. 어떤 방식이든 최적화한 풀이 방식으로 요구 조건에 맞게 논리적인 구현이 가능하면 된다는 거다.

 

나의 경우에는 일단 d, l, r, u 순서 조건을 고려하여 정답 문자열을 구성하고자 했다.

1) S→ E로 가는 방향의 구성은 고정되어 있다는 점을 활용했다.

• 예를 들어, 입출력 예시 1번에서 S→E로 가는 경로는 (2,3) → (3, 1)로 총 3칸을 가야 한다. 이떄 어떤 순서로 가든 3칸을 (아래, 옆, 옆)의 구성으로 가야하는 건 변함이 없다는 점을 활용해서 그 구성은 반드시 포함하도록 했다.
• 따라서 각 방향에 맞는 구성 개수를 <방향, 개수> 형태로 HashMap에 담았다.

2) 고정된 방향 구성이 k칸보다 크거나, (k-구성칸) 값이 홀수인 경우에는 어떤 방법으로도 k칸으로 E에 도달할 수 없음을 의미한다.

• 즉, 예시 1번을 토대로 (2,3) → (3,1) 을 가는 방법은 3칸 (아래, 옆, 옆) 이고, k는 5이므로 2칸에 대해 어떤 의미없는 행동으로 왕복을 해야하는데, 그 값이 홀수이면 왕복이 안된다. 그래서 impossible을 리턴하도록 했다.

3) 이제 k칸에서 고정된 경로를 제외한 칸수만큼 의미없는 행위 문자열을 구성하며 k칸으로 E에 도착하는 String 문자열을 구성해야 하고, 이왕이면 사전 앞순으로 구성해야 한다.

→ 방법은 d, l, r, u 순으로 각 문자로 구성할 수 있는 문자를 최대한 구성해놓는 방식으로 쭉 실행하다보면 사전 앞순이 구성되는 것을 활용했다.

💚 제출 코드

import java.util.*;
class Solution {
    private int[][] map;
    private Map<String, Integer> hashMap;
    private String answer = "";
    
    //구성 만드는 함수 
    private void setMap(int upDown, int leftRight){
        //구성을 문자열로 만들어주기 
        hashMap = new HashMap<>();
        hashMap.put("d",0);
        hashMap.put("l", 0);
        hashMap.put("r", 0);
        hashMap.put("u", 0);
        
        if(upDown < 0){ //음수이면 위
            hashMap.put("u", Math.abs(upDown));
        }
        if(upDown > 0){//양수이면 아래
            hashMap.put("d", Math.abs(upDown));
        }
        if(leftRight < 0){//음수이면 왼쪽
            hashMap.put("l", Math.abs(leftRight));
        }
        if(leftRight > 0){
            hashMap.put("r", Math.abs(leftRight));
        }
    }
    //정답 구성함수
    private void addAnswer(String c, int count){
        for(int i=0; i<count; i++){
            answer += c;
        }
    }
    
    //솔루션 함수 
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        //1) S -> E 
        int upDown = r - x; //음수 : 위, 양수 : 아래 
        int leftRight = c -y; //음수  : 왼, 양수 : 오른쪽
        //target = 구성의 절대적 수 a
        int target = Math.abs(upDown) + Math.abs(leftRight);
        
        //2) k와 target 비교
        if ( k < target || (k - target) % 2 == 1) return "impossible";
        
        // 의미없는 행동 해야하는 개수
        int notMean = k - target;
        
        setMap(upDown, leftRight);
        
        //3) 이동 문자 구성
        //d로 일단 가고 
        addAnswer("d", hashMap.get("d"));
        
        //d로 더 갈 수 있는지 개수 (의미없이 구성/2 로 d하나 구성하면 u도 구성해줘야 하기 때문에
        // notMean/2 값과 아래 최대 n-고정 구성 d 하고 더 갈 수있는 d방향 칸을 비교해서 더 작은 값으로 구성한다.)        
        int dMin = Math.min(notMean/2, n - (x + hashMap.get("d")));
        
        addAnswer("d", dMin);
        
        //u도 (d)만큼 의미없이 간 거 되돌아오기 위함 
        int tmp = hashMap.get("u");
        tmp += dMin;
        hashMap.put("u", tmp);
        
        notMean -= (dMin * 2);//d-u 왕복한 개수를 (했다 치는거)
        
        //l로 일단 가고
        addAnswer("l", hashMap.get("l"));
        int lMin = Math.min(notMean/2, (y - hashMap.get("l") - 1));
        
        addAnswer("l", lMin);
        
        //r도 (l)만큼 의미없이 간 거 되돌아오기 위함
        hashMap.put("r", hashMap.get("r") + lMin);
        notMean -= (lMin * 2);
        //이건 rlrl이 rrll보다 사전 앞순이므로 이런 식으로 붙인 거다.
        addAnswer("rl", notMean/2); 
        
        //이제 map에 담긴 (origin 구성을 털기)
        addAnswer("r", hashMap.get("r"));
        //이제 map에 담긴 origin u
        addAnswer("u", hashMap.get("u"));
        
        
        return answer;
    }
}

💚 회고

어려웠다. 그래서 나도 코드 구현하는 과정에서 계속 다른 사람의 코드도 활용해보고 참고하면서 완성했다. 더 논리적으로 경우의 수를 나눠 코드로 구현하는 연습을 해야할 것 같다.