[프로그래머스 Level.3] 미로 탈출 명령어 (2023 KAKAO BLIND RECRUITMENT) (Java)

문제 링크

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

프로그래머스

 

 

 

 

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

 

 

 

문제 설명

 

 

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

 

단, 미로를 탈출하는 조건이 세 가지 있습니다.

 

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

 

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

 

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

 

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

 

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

 

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

 

....
..S.
E...

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

 

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

 

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

 

---

제한사항

• 2 ≤ n (= 미로의 세로 길이) ≤ 50
• 2 ≤ m (= 미로의 가로 길이) ≤ 50
• 1 ≤ x ≤ n
• 1 ≤ y ≤ m
• 1 ≤ r ≤ n
• 1 ≤ c ≤ m
• (x, y) ≠ (r, c)
• 1 ≤ k ≤ 2,500

 

---

 

입출력 예

n	m	x	y	r	c	k	result
3	4	2	3	3	1	5	"dllrl"
2	2	1	1	2	2	2	"dr"
3	3	1	2	3	3	4	"impossible"

 

---

입출력 예 설명

 

입출력 예 #1

 

문제 예시와 동일합니다.

 

 

 

입출력 예 #2

 

미로의 크기는 2 x 2입니다. 출발 지점은 (1, 1)이고, 탈출 지점은 (2, 2)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

 

S.
.E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (2, 2)입니다.

 

탈출까지 이동해야 하는 거리 k가 2이므로 다음과 같은 경로로 탈출할 수 있습니다.

1. rd
2. dr

 

"dr"이 사전 순으로 가장 빠른 경로입니다. 따라서 "dr"을 return 해야 합니다.

 

 

 

입출력 예 #3

 

미로의 크기는 3 x 3입니다. 출발 지점은 (1, 2)이고, 탈출 지점은 (3, 3)입니다.

빈 공간은 ., 출발 지점을 S, 탈출 지점을 E로 나타내면 다음과 같습니다.

 

.S.
...
..E

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 3)입니다.

 

탈출까지 이동해야 하는 거리 k가 4입니다. 이때, 이동 거리가 4이면서, S에서 E까지 이동할 수 있는 경로는 존재하지 않습니다.

 

따라서 "impossible"을 return 해야 합니다.

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";

        int minDist = Math.abs(x - r) + Math.abs(y - c); // 최단 거리

        k -= minDist; // k에서 최단 거리만큼 뺌

        if(k < 0 || k % 2 == 1) return "impossible";
        
        Map<Character, Integer> map = new HashMap<>();

        // 출발점에서 도착점까지 durl 횟수 카운팅
        if(x > r) // 좌표상 더 큰게 더 아래에 있으므로
            map.put('u', map.getOrDefault('u', 0) + x - r);
        else
            map.put('d', map.getOrDefault('d', 0) + r - x);

        if(y > c)
            map.put('l', map.getOrDefault('l', 0) + y - c);
        else
            map.put('r', map.getOrDefault('r', 0) + c - y);

        // d부터 이동하는게 사전순으로 제일 빠르므로 출발점에서 도착점까지 d 횟수만큼 이동
        int dCnt = map.getOrDefault('d', 0); 
        for(int i=0; i<dCnt; i++) answer += "d";

        // 출발점에서 d만 이동한 좌표에서 d 갈 수 있는만큼 더 d 이동 (좌표상 더 d 이동할 수 있는 횟수와 k/2와 비교)
        int addD = Math.min(n - (x + dCnt), k / 2); 
        for(int i=0; i<addD; i++) answer += "d";

        // 추가로 d 이동한만큼 u 이동해야하니까 추가로 d 이동한만큼 u 횟수 추가
        map.put('u', map.getOrDefault('u', 0) + addD); 
        
        // k에서 추가로 d와 u 왕복한 만큼 감소
        k -= 2 * addD; 

        // d 다음에는 l이 사전순으로 빠르므로 l도 마찬가지로 먼저 이동
        int lCnt = map.getOrDefault('l', 0); 
        for(int i=0; i<lCnt; i++) answer += "l";

        // 출발점에서 d만 전부 이동 후에 l만큼 이동한 상황에서 더 갈 수 있는 l 계산 (사전순으로 d l r u 순으로 빠르므로)
        int addL = Math.min((y - lCnt) - 1, k / 2); // 1이 왼쪽 시작 좌표이므로 (y - lCnt) - 1 로 계산해서 비교
        for(int i=0; i<addL; i++) answer += "l";

        // 추가로 l 이동한만큼 u 이동해야하니까 추가로 l 이동한만큼 r 횟수 추가
        map.put('r', map.getOrDefault('r', 0) + addL);
        
        // k에서 추가로 l과 r 왕복한 만큼 감소
        k -= 2 * addL;

        // k가 남아있으면 rl로 나머지 k 소진 (l이 사전순 제일 빠르므로 lr을 추가해야하지만 지금 제일 왼쪽으로 간 상태이므로 rl로 추가)
        for(int i=0; i<k/2; i++) answer += "rl";

        // r 횟수만큼 이동
        for(int i=0; i<map.get('r'); i++) answer += "r";

        // u 횟수만큼 이동
        for(int i=0; i<map.get('u'); i++) answer += "u";

        return answer;
    }
}


// dfs 풀이 참고 : https://0713k.tistory.com/52
class Solution2 {
    Character[] posChar = {'d','l','r','u'};
    int[] dx = {1, 0, 0, -1}; // d l r u
    int[] dy = {0, -1, 1, 0};
    boolean stop = false;
    String answer = "impossible";
    int n, m, r, c;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        this.n = n;
        this.m = m;
        this.r = r - 1; // 격좌 좌표가 (1, 1) 시작이므로 인덱스로 맞추기 위해 감소
        this.c = c - 1;

        if(!canArrival(x-1, y-1, k)) return answer;
        
        dfs(x-1, y-1, k-1, "");
        
        return answer;
    }
    
    // 나머지 움직일 수 있는 횟수로 도착할 수 있는지 확인
    public boolean canArrival(int nx, int ny, int k) {
        int dist = Math.abs(nx - r) + Math.abs(ny - c);
        
        if(dist > k || (k - dist) % 2 == 1) return false;
        
        return true;
    }

    public void dfs(int x, int y, int cnt, String cur) {
        if(stop || cnt < 0) return;

        for(int i=0; i<4; i++) {
            if(stop) return;
            
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 좌표 범위를 벗어나거나 남은 횟수가 도착할 수 없다면 종료
            if(nx < 0 || ny < 0 || nx >= n  || ny >= m || !canArrival(nx, ny, cnt)) continue;
            
            if(cnt > 0) dfs(nx, ny, cnt - 1, cur + posChar[i]);
            
            if(nx == r && ny == c && cnt == 0) {
                stop = true;
                answer = cur + posChar[i];
                return;
            }
        }
    }
}

 

풀이

1. 우선 출발점에서 도착점까지의 최소 거리 minDist를 구한다.
2. k에서 minDist를 뺀 나머지는 추가로 돌아다닐 수 있는 거리이다. (사전순으로 'd', 'l', 'r', 'u' 순으로 앞에 있기 때문에 빠르게 추가로 돌아다니려면 아래로 내려갔다('d') 위로 올라갔다('u')를 반복하거나 아래로 갈 수 없다면 왼쪽으로 갔다가('l') 오른쪽으로 가는 것('r')을 반복해야한다)
3. 따라서 k가 minDist보다 작으면 출발점에서 도착점에 도달할 수 없고 k에서 minDist를 뺀 나머지가 홀수라면 추가로 돌아다녀도 도착점에 도달할 수 없기 때문에 "impossible"을 반환한다. (도착점에서 추가로 왕복하는 경우도 짝수 칸이 필요하고 주변을 돌아도 짝수 칸이 필요하다)
4. 이제 Map을 생성하고 출발점(x, y)에서 도착점(r, c)까지 두 좌표의 크기를 비교해서 'd', 'l', 'r', 'u'를 카운팅하여 넣는다. 
5. 사전순으로 'd', 'l', 'r', 'u' 순으로 앞에 있기 때문에 움직일 수 있는 횟수 내에서 'd'부터 최대한 이동한다.
   우선 Map에서 최단거리에는 'd' 이동이 없어 안담겨져 있을 수도 있으므로 getOrDefault()를 이용하여 'd'의 이동 횟수를 가져오고 해당 횟수만큼 아래로 이동하고 answer에 추가한다.
6. 그리고 여기서 'd'를 더 이동할 수 있는만큼 이동해야 한다. 더 내려가면 내려간만큼 올라가야 하므로 k를 2로 나눈만큼만 가야 다시 올라올 수 있다. 따라서 현재 좌표에서 좌표 범위상 'd'만큼 이동할 수 있는 횟수와 k를 2로 나눈 수중에 작은 수만큼 아래로 더 이동하고 해당 횟수만큼 answer에 'd'를 추가한다.
7. 추가로 아래로('d') 더 이동한만큼 위로('u') 더 이동해야 하므로 'u'를 key로 하는 Map에 해당 횟수만큼 더 추가해주고 k에서 해당 왕복 횟수만큼을 감소시킨다.
8. 그리고 'd' 다음으로 'l'(왼쪽)을 이동할 수 있는만큼 이동하도록 한다. 'd'와 마찬가지로 Map에서 'l'의 횟수만큼 가져와 이동하고 answer에 추가한 후에 좌표 범위상 'l'을 더 이동할 수 있는 횟수와 남은 k를 2로 나눈 수와 비교하여 작은 수만큼을 더 왼쪽으로 이동하고 answer에 추가한다.
9. 또한, 이것도 마찬가지로 왼쪽('l)으로 추가로 더 이동한만큼 오른쪽('r')으로 더 이동해야하므로 'r'을 key로 하는 Map에 해당 횟수만큼 더 추가해주고 k에서 해당 왕복 횟수만큼을 감소시킨다.
10. 그리고 아직도 k가 남아있다면 오른쪽('r')으로 갔다 왼쪽('l')으로 갔다를 반복하여 남은 k를 소진하면 된다. (현재 맨 아래로 내려간 후에 맨 왼쪽으로 갔음(ddd...llll...)에도 k가 남아있는 상태이기 때문에 사전순으로 가장 빠르게 하려면 ud 보다는 rl을 반복해야 한다)
11. 그 후에 Map에서 'r'의 횟수를 가져와 해당 횟수만큼 이동하므로 answer에 'r'을 추가해준다.
12. 마지막으로 Map에서 'u'의 횟수를 가져와 해당 횟수만큼 이동하므로 answer에 'u'를 추가해주면 k만큼 이동하여 사전순으로 제일 빠른 루트가 완성된다.

 

 

 

참고

https://github.com/Juniork725/coding_test/blob/main/%EB%82%9C%EC%9D%B4%EB%8F%843/%EB%AF%B8%EB%A1%9C%20%ED%83%88%EC%B6%9C%20%EB%AA%85%EB%A0%B9%EC%96%B4.md