프로그래머스 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. 주어진 미로에서 출발 지점 (x, y)에서 도착 지점 (r, c)까지 이동하는 경로 중에서 조건에 맞는 경로를 찾습니다.

 

2. 출발 지점에서 도착 지점까지의 최단 거리를 계산하고, 거리 k로 도달할 수 없거나 k가 최단 거리보다 짧으면 "impossible"을 반환합니다.

 

3. 깊이 우선 탐색 (DFS)을 사용하여 경로를 탐색하고, 경로의 길이가 k인 경우 결과를 저장하고 반환합니다.

 

4. 이동 방향은 dir 배열에 문자로 저장되어 있으며, 각 방향에 따라 행과 열의 변화가 rdir와 cdir 배열에 저장되어 있습니다.

 

5. 재귀 호출을 통해 다음 이동을 시도하고, 경로를 탐색하며 이동 방향을 경로에 추가하고 제거하면서 모든 가능한 경로를 확인합니다.

 

import java.util.*;

class Solution {
    int[][] array;
    String answer = null;
    StringBuilder route;
    char[] dir = {'d', 'l', 'r', 'u'}; // 이동 방향을 나타내는 문자 배열
    int[] rdir = {1, 0, 0, -1}; // 행 이동 방향 배열
    int[] cdir = {0, -1, 1, 0}; // 열 이동 방향 배열
    int endRow, endCol; // 도착 지점의 행과 열
    int arrRow, arrCol; // 미로의 행과 열 길이

    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        route = new StringBuilder();
        array = new int[n][m];
        endRow = r;
        endCol = c;
        arrRow = n;
        arrCol = m;

        // 출발 지점에서 도착 지점까지의 최단 거리 계산
        int length = distance(x, y, r, c);

        // 거리 k로 도달할 수 없거나, k가 최단 거리보다 짧으면 불가능한 경우
        if ((k - length) % 2 == 1 || k < length)
            return "impossible";

        dfs(x, y, 0, k); // 깊이 우선 탐색으로 경로를 찾습니다.

        return answer == null ? "impossible" : answer;
    }

    private int distance(int x, int y, int r, int c) {
        return (int) Math.abs(x - r) + (int) Math.abs(y - c);
    }

    private void dfs(int r, int c, int depth, int k) {

        if (answer != null)
            return; // 이미 경로를 찾은 경우 중단합니다.

        if (depth + distance(r, c, endRow, endCol) > k)
            return; // 현재 깊이 + 남은 거리 > k 인 경우 중단합니다.

        if (k == depth) {
            answer = route.toString(); // 경로의 길이가 k인 경우 결과를 저장하고 반환합니다.
            return;
        }

        for (int i = 0; i < 4; i++) {

            int nextRow = r + rdir[i];
            int nextCol = c + cdir[i];

            // 다음 이동 좌표가 미로 내부에 있는지 확인합니다.
            if (nextRow <= arrRow && nextCol <= arrCol && nextRow > 0 && nextCol > 0) {
                route.append(dir[i]); // 경로에 이동 방향을 추가합니다.
                dfs(nextRow, nextCol, depth + 1, k); // 재귀 호출을 통해 다음 이동을 시도합니다.
                route.delete(depth, depth + 1); // 경로에서 이동 방향을 제거하여 다른 경로를 시도합니다.
            }
        }
    }
}