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

1.  문제 링크

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

2.  문제

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

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

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

• 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 해야 합니다.

3.  제한사항

• 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

입출력 예

4.  소스코드

class Solution {
    static final char[] DIRECTION = {'d', 'l', 'r', 'u'};
    static final int[][] DIRECTION_MOVE = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    int rowNum, colNum, endX, endY;
    String answer;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        rowNum = n; colNum = m;
        endX = r - 1; endY = c - 1;
        answer = "";
        int difference = Math.abs(x - r) + Math.abs(y - c);

        dfs(x - 1, y - 1, k, "", difference);

        if(answer.equals("")) answer = "impossible";
        return answer;
    }

    public boolean dfs(int x, int y, int k, String moves, int difference) {
        if(k == 0 && difference == 0) {
            answer = moves;
            return true;
        }
        for(int dir = 0; dir < 4; dir++) {
            int cx = x + DIRECTION_MOVE[dir][0], cy = y + DIRECTION_MOVE[dir][1];

            if(isInMap(cx, cy) && difference <= k) {
                if(difference % 2 == k % 2) {
                    if(dfs(cx, cy, k - 1, moves + DIRECTION[dir], Math.abs(cx - endX) + Math.abs(cy - endY)))
                        return true;
                }
            }
        }

        return false;
    }

    public boolean isInMap(int x, int y) {
        if(x >= 0 && x < rowNum && y >= 0 && y < colNum) return true;
        return false;
    }
}

5.  접근

• 사전 순으로 빠른 경로로 탈출해야 하기 때문에 이동과 관련된 배열인 DIRECTION과 DIRECITON_MOVE를 작성할 때, d, l, r, u 순으로 작성해줍니다.
• DFS를 통해서 시작점에서 도착점까지 k번 이동하여 갈 수 있는지를 판단해야하는데, 정확히 k번을 이동해야 하고, 방문했던 곳을 다시 방문한다는 점에서 방문 체크를 할 수 없으니 예외 케이스를 어떻게 잡아야 하는지 감이 잘 잡히지 않았습니다...
• 다른 분들의 코드를 참고한 결과, 두 가지의 경우를 이용하여 예외 케이스를 판단할 수 있었습니다.
  • 특정 위치에서 도착점까지의 거리를 difference라고 했을 때, 남은 이동 횟수가 홀수인데 difference가 짝수이거나, 남은 이동 횟수가 짝수인데 difference가 홀수라면 남은 이동 횟수를 이용하여 도착점까지 갈 수 없으므로 이러한 경우는 더이상 탐색해보지 않아도 되는 케이스가 됩니다.
  • 또한, 특정 위치에서 도착점까지의 거리가 남은 이동 횟수보다 크다면 애초에 도착점까지 이동할 수 없기 때문에 이러한 경우 역시 더이상 탐색해보지 않아도 되는 케이스가 됩니다.
• 위 두 경우를 이용하여 DFS를 통해 사전 순으로 가장 빠른 경로를 찾습니다.
  • 처음 이동과 관련된 배열을 사전 순으로 정렬하여 작성하였기 때문에 한 번 도착점까지 도착한다면 그 경로가 사전 순으로 가장 빠른 경로가 되므로 한 번 도착했다면 그 이후부터는 탐색을 진행하지 않습니다.