골드에그

1. 문제요약

코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 (programmers.co.kr)

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

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

출발 위치, 도착 위치, 총 거리 K 가 주어질 때, 미로를 탈출하기 위한 경로를 구하시오.

2. 문제예제

문제 지문에 잘 나와있으므로 생략한다.

3. 팩트추출

Fact 1 : 사전 순으로 출력되려면 항상 d => l => r => u 순으로 탐색해야 한다. 지금 탐색 순서가 실패하면 아래 단계 순번으로 탐색하다가 다시 윗 단계 순번으로 탐색해야 한다.

Fact 2 : 2차원 배열로 구성되어 있는 그래프를 탐색하는데 위와 같이 특정한 조건이 존재하면 DFS 로 탐색하는 것이 좋다.

특정한 조건이란, 모두 비교하지 않고 도착이 가능한 형태인지 체크하는 문제이거나, 체인 형태로 탐색하는 순서(조건 존재)가 있는 경우이다. 해당 문제와 같이 실패했을 때도 탐색하는 순서가 정해져있다면 금상첨화다.

Fact 3 : 가지치기를 할 수 있다. 현재 위치에서 도착 위치까지 남은 거리와 남은 k 가 같은 짝수이거나 홀수이어야 한다. 짝 /홀이 다르다면, 어차피 도착을 못 하기 때문에 더 이상 탐색할 필요가 없다.

4. 문제전략

d => l => r => u 순서로 dfs 탐색하고 현재 위치에서 도착 위치까지 남은 거리와 남은 k 거리를 비교한다.

5. 소스코드

import java.util.*;

class Solution {
        // d, l, r, u 순으로 탐색
    private static final int[] dx = { 1, 0, 0, -1};
    private static final int[] dy = { 0, -1, 1, 0};
    private static final String[] term = {"d", "l", "r", "u"};
    private static int mapX, mapY;
    private static int endX, endY;
    private String tempAnswer = "";

    public boolean dfs(int x, int y, int k, String str, int diff) {
        if(k==0 && diff==0){
            tempAnswer = str;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX >=0 && nextY >= 0 && nextX < mapX && nextY < mapY && diff<=k) {
                if ((diff % 2 == 0 && k % 2 ==0) || (diff % 2 == 1 && k % 2 ==1)) {
                    if (dfs(nextX, nextY, k - 1, str + term[i], Math.abs(nextX - endX) + Math.abs(nextY - endY))) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer;
        mapX = n;
        mapY = m;
        endX = r-1;
        endY = c-1;
        int diff = Math.abs((r-1)-(x-1)) + Math.abs((c-1)-(y-1));
        dfs(x-1, y-1, k, "", diff);
        if(tempAnswer.equals("")){
            answer = "impossible";
        } else {
            answer = tempAnswer;
        }
        return answer;
    }
}