[프로그래머스 / Java] 미로 탈출 명령어

문제 정보

• 난이도: level. 3

• 예상 태그: 백트래킹, dfs

• 소요 시간: 1h 30m

풀이

1. 불가능한 경우 판정
   불가능한 경우는 다음 두 가지 케이스가 있다. 편의상 시작 좌표(x, y)와 끝나는 좌표 (r, c) 사이의 거리를 dist(s, e)라고 하겠다.
   (i) k < dist(s,e)인 경우. => 움직일 수 있는 숫자인 k가 거리보다 더 작은 것이기 때문에 어떻게 해도 도착을 할수가 없다.
   (ii) k % 2 != dist(s,e) % 2인 경우. => 만약 k가 dist보다 크다면 왔다갔다 (d,u 또는 l,r 등등)를 해야한다 근데 k와 dist를 2로 나눈 나머지가 상이하다면 도착을 할 수가 없게 된다.

나는 저 중에 (i)의 경우를 생각하지 못했다....

2. 가장 짧은 경우
   알파벳 순으로 'd', 'l', 'r', 'u'이므로, [아래, 왼, 오, 위] 순으로 방문하도록 dy, dx 배열의 순서를 조정해야한다.

import java.util.*;

class Solution {
    static int sx, sy, ex, ey, len;
    static int ln, lm;
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, -1, 1, 0};
    static String[] di = {"d", "l", "r", "u"};
    static String ans = null;
    public String solution(int n, int m, int x, int y, int r, int c, int k) {

        sx = x; sy = y; ex = r; ey = c; len = k;
        ln = n; lm = m;

        // 가능 불가능 판별
        if((Math.abs(sx-ex) + Math.abs(sy-ey)) % 2 != k%2) {
            return "impossible";
        }

        if((Math.abs(sx-ex) + Math.abs(sy-ey)) > k) return "impossible";
        dfs(sx, sy, new StringBuffer(""));

        return ans;
    }

    public static void dfs(int cx, int cy, StringBuffer s) {
        // 가지치기 1
        if(ans != null) return;

        if(s.length() == len && cx == ex && cy == ey) {
            ans = s.toString();
            return;
        } else if(s.length() == len) return;

        // 가지치기 2
        int dist = Math.abs(ex-cx) + Math.abs(ey-cy);
        if(len - s.length() < dist) return;


        for(int i=0; i<4; ++i) {
            int nx = cx + dx[i], ny = cy + dy[i];
            if(nx < 1 || nx > ln || ny < 1 || ny > lm) {
                continue;
            }

            s.append(di[i]);

            dfs(nx, ny, s);
            s.delete(s.length()-1, s.length());
        }

    }
}

위 코드를 보면 dfs를 돌리기 전부터 출발-도착의 거리를 2로 나눈 나머지와 k를 2로 나눈 나머지를 비교하여 가능, 불가능을 판정할 수 있다.

dfs 안에서는

• 가지치기 1: ans가 정답 문자열인데 null이 아니라면 이미 정답 문자열이 만들어져 있는 것이므로 더이상 볼필요가 없으니 함수를 빠져나간다. dy, dx를 알파벳 순으로 빠른 것부터 정렬해놓았으니 당연히 처음 만들어진 정답 문자열이 알파벳 사전상 가장 빠른 것이 되기 때문이다.
• 가지치기 2: 현재 위치-도착 위치의 거리를 계산하여 k 보다 멀다면 빠져나온다

자체 피드백

dfs로 풀릴까..? 싶었는데 가지치기를 잘 해야 dfs로 풀리는 문제였다.

나는 가지치기 1, 2를 생각해내지 못했다. 당연히 dy, dx를 잘 만들어놓았으므로, 가장 먼저 방문한 루트로 만들어진 문자열이 사전 순으로 가장 앞선다는 것, 현재 있는 곳에서의 거리가 k보다 크면 더 볼 필요 없다는것을 생각하지 못했다

백트랙킹을 다시 만나면 가지치기 조건들이 뭐가 있을지 꼼꼼하게 생각해 보아야겠다.