[Programmers/Level 3] 미로 탈출 명령어(Java)

문제 링크

프로그래머스

 

문제

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

3 4
2 3 3 1
5

예제 출력 1

dllrl

예제 입력 2

2 2
1 1 2 2
2

예제 출력 2

dr

예제 입력 3

3 3
1 2 3 3
4

예제 출력 3

impossible

 

알고리즘 분류

• 그리디 알고리즘
• 그래프 탐색

 

풀이

최대한 사전 순으로 이동 경로를 만들기 위해서는 방향을 사전 순으로 정렬해야 한다.

왼쪽이 l, 오른쪽이 r, 위쪽이 u, 아래쪽이 d이므로, 아래쪽, 왼쪽, 오른쪽, 위쪽(d, l, r, u) 순으로 정렬한다.

그리고 BFS로 4방향 탐색을 한다.

처음에 아래쪽으로 이동할 수 있다면, 굳이 다음 방향부터는 탐색하지 않아도 된다. 아래쪽으로 이동할 수 있으면 해당 경로가 사전 순으로 가장 앞서는 경로이기 때문이다.

또한, 이동 횟수를 K보다 넘지 않도록 제한한다.

마지막으로 남은 이동 횟수와 현재 위치에서 도착 지점까지의 맨해튼 거리의 차가 홀수라면, 도착 지점까지 도달할 수 없기 때문에 그 쪽으로는 이동이 불가능하므로 이동하지 않는다.

 

해결 완료 시각

 

코드

import java.util.*;

class Solution {
    
    private static class Info {
        
        int Y, X, C;
        String S;
        
        public Info(int Y, int X, int C, String S) {
            super();
            this.Y = Y;
            this.X = X;
            this.C = C;
            this.S = S;
        }
    }
    
    private static int N, M, Y, X, R, C, K;
    private static boolean[][][] visited;
    private static int[] moveY = { 1,0,0,-1 };
    private static int[] moveX = { 0,-1,1,0 };
    private static String[] dirs = { "d","l","r","u" };
    private static String Answer = "impossible";
    
    private static void init() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < (K + 1); k++) {
                    visited[i][j][k] = false;
                }
            }
        }
    }
    
    private static boolean isInOfRange(int y, int x) {
        return ((y >= 0) && (y < N) && (x >= 0) && (x < M));
    }
    
    private static void bfs() {
        Queue<Info> queue = new LinkedList<>();
        queue.add(new Info(Y, X, 0, ""));
        visited[Y][X][0] = true;
        
        while (!queue.isEmpty()) {
            Info now = queue.poll();
            int nowY = now.Y;
            int nowX = now.X;
            int nowC = now.C;
            String nowS = now.S;
            
            if ((nowY == R) && (nowX == C) && (nowC == K)) {
                Answer = nowS;
                return;
            }
            
            for (int i = 0; i < 4; i++) {
                int nextY = nowY + moveY[i];
                int nextX = nowX + moveX[i];
                int remain = K - (nowC + 1);
                if (isInOfRange(nextY, nextX) && (K >= nowC + 1) && !visited[nextY][nextX][nowC + 1]) {
                    int remainDistance = Math.abs(nextY - R) + Math.abs(nextX - C);
                    if ((remain >= remainDistance) && ((remain - remainDistance) % 2 == 0)) {
                        visited[nextY][nextX][nowC + 1] = true;
                        queue.add(new Info(nextY, nextX, nowC + 1, nowS + dirs[i]));
                        break;
                    }
                }
            }
        }
    }
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        visited = new boolean[n][m][k + 1];
        N = n;
        M = m;
        Y = x - 1;
        X = y - 1;
        R = r - 1;
        C = c - 1;
        K = k;
        init();
        bfs();
        
        return Answer;
    }
}