[level 3] 미로 탈출 명령어 - 150365

문제 링크

성능 요약

메모리: 81.4 MB, 시간: 6.45 ms

구분

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 10월 16일 22:49:41

문제 설명

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

입출력 예

입출력 예 설명

입출력 예 #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 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이

• BFS로 했다가 메모리 초과...
  질문하기를 대충 봤는데 BFS는 시간초과 났다는 글이 많음

• 수학적으로 접근하기로 방식 변경
  사전순으로 경로 탐색이 될라면 아래 왼쪽 오른쪽 위 순서로 탐색해야 함.

• 아래는 가장 우선순위가 크기에 무조건 먼저 나와야함
  그 다음에는 왼쪽이고 왼쪽 경계까지 도달하면 오른쪽 왼쪽 왕복해야 함.
  그 다음에는 오른쪽으로 필수 이동
  남은거 합치고 위로 이동

코드

import java.util.Queue;
import java.util.ArrayDeque;

class Solution {
    
    public static class P {
        int x, y;
        
        public P(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int N, M; // 격자 크기
    public static String path, suffix; // path: 경로, suffix: 짝꿍이 되는 뒤의 경로
    public static int cnt; // 탈출 지점에 도달하고도 추가로 움직여야 하는 움직임 쌍의 개수 (무의미한 왔다갔다 이동 수)
    
    // down,left,right,up 알파벳 오름차순 순서
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        N = n;
        M = m;
        
        int dx = r - x;
        int dy = c - y;
        
        int dist = Math.abs(dx) + Math.abs(dy); // 맨하탄 거리
        
        // 맨하탄 거리보다 k가 작으면 impossible
        if (k < dist)
            return "impossible";
        // k에서 맨하탄 거리 빼고 남은 값이 홀수면(쌍이 안되면) impossible
        if ((k - dist) % 2 == 1) {
            return "impossible";
        }
        
        path = "";
        suffix = "";
        
        P p = new P(x, y); // 시작 위치
        cnt = (k - dist) / 2; // 도착지까지 반드시 필요한 이동 외에 소모해야 할 움직임 쌍의 개수
        
        // 필수로 아래로 가야하는 움직임
        if (dx > 0) {
            p.x += dx;
            
            while (dx != 0) {
                path += "d";
                dx--;
            }
        }
        
        goDown(p); // 아래로 더 갈 수 있으면 더 가고 suffix에 반대 쌍인 위로 가기 역순으로 추가
        
        // 필수로 왼쪽으로 가야하는 움직임
        if (dy < 0) {
            p.y += dy;
            
            while (dy != 0) {
                path += "l";
                dy++;
            }
        }
        
        goLeft(p); // 왼쪽으로 더 갈 수 있으면 더 가고 suffix에 반대 쌍인 오른쪽으로 가기 역순으로 추가
        
        goRight(p); // rlrl... 반복 (rrr..lll 보다 rlrlrl...이 사전순으로 앞에온다.)
            
        // 필수로 오른쪽으로 가야하는 움직임
        if (dy > 0) {
            p.y += dy;
            
            while (dy != 0) {
                path += "r";
                dy--;
            }
        }
       	
        path += suffix; // path에 suffix 쌍(ex. rrr..uuu..) 합치기
        
        // 필수로 위쪽으로 가야하는 움직임
        if (dx < 0) {
            p.x += dx;
            
            while (dx != 0) {
                path += "u";
                dx++;
            }
        }
        
        return path;
    }
    
    public static void goDown(P p) {
        while (cnt > 0) {
            if (p.x + 1 <= N) {
                path += "d";
                suffix = "u" + suffix;
                p.x++;
                cnt--;
            } else {
                break;
            }
        }
    }
    
    public static void goLeft(P p) {
        while (cnt > 0) {
            if(p.y - 1 >= 1) {
                path += "l";
                suffix = "r" + suffix;
                p.y--;
                cnt--;
            } else {
                break;
            }
        }
    }
    
    public static void goRight(P p) {
        while (cnt > 0) {
            if(p.y + 1 <= M) {
                path += "rl";
                cnt -= 1;
            } else {
                break;
            }
        }
    }
}