[프로그래머스] 미로탈출명령어 (java)

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/150365?language=java

프로그래머스

---

 

2. 풀이

키워드 : DFS, 백트래킹, 가지치기

이 문제는 dfs 와 백트래킹을 같이 이용해서 푸는 문제였다. 

출발점 - 도착점 까지의 거리를 맨해튼 거리라고 한다. 

dfs 를 이용하는 것 까진 알겠는데 백트래킹을 이용할 때 어떤 부분들을 가지치기를 할 수 있을까?

가지치기를 어떻게 할 것인가?

- 남은거리가 맨해튼 거리보다 작은 경우 (diff < manhattenDistance)

- 남은거리 % 2 != k % 2인 경우

   - 만약 k가 dist보다 크다면 왔다갔다 (d,u 또는 l,r 등등)를 해야하는데 나머지가 다르다면 제대로 도착할 수 없다는 의미가 된다.

 

---

3. 소스코드

import java.util.*;

class Solution {
    private static int[][] dir = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; // 동남서북 rdlu
    private String answer = "impossible";
    private int r;
    private int c;
    private int n;
    private int m;
    private int k;
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        this.r = r;
        this.c = c;
        this.n = n;
        this.m = m;
        this.k = k;
        
        if(getManhattanDist(x,y) > k) {
            return answer; // 맨해튼거리가 더 크다면 정답을 구할 수 없으므로 impossible
        }
        // 맨해튼거리를 2로 나눈 나머지와 K 를 2로 나눈 나머지가 같지 않은 경우 impossible
        if(getManhattanDist(x,y) % 2 != k % 2) return answer;
        
        dfs(0, x, y, "");
        
        System.out.println(answer);
        return answer;
    }
    
    private void dfs(int moveDist, int x, int y, String command) {
        if(!answer.equals("impossible")) return; // 이미 미로를 탈출한 경우
        if(k - moveDist < getManhattanDist(x,y)) return;
        
        if(moveDist == k) {
            answer = command;
            return;
        }
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            char newCommand = getCommand(i);
            if(isOutOfRange(nx, ny)) {
                continue;
            }
            
            dfs(moveDist + 1, nx, ny, command + newCommand);
        }    
    }
    
    private int getManhattanDist(int x, int y) {
        return Math.abs(r-x) + Math.abs(c-y);
    }
    
    private char getCommand(int i) {
        return switch (i) {
            case 0 -> 'd';
            case 1 -> 'l';
            case 2 -> 'r';
            default -> 'u';
        };
    }

    private boolean isOutOfRange(int x, int y) {
        return x < 1 || y < 1 || x > n || y > m;
    }
}

 

참고

- https://given-dev.tistory.com/91

[Programmers-Java] 미로 탈출 명령어