프로그래머스 Lv3 미로 탈출 명령어

📘 문제 설명

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

📘 요구 사항

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

📖 문제 해결 전략

• k번째에 원하는 지점에 서 있을 수 있는 수많은 경우의 수 중에서 사전 순으로 가장 빠른 경로를 찾기 위해서, d, l, r, u 순으로 해당 방향으로 이동 가능한지 greedy하게 문제를 해결할 수 있다.

    while(k-- > 0){
        for(int i = 0; i < 4; i++){
            int nx = x + dirx[i];
            int ny = y + diry[i];
            int remain = Math.abs(nx - r) + Math.abs(ny - c);
              
            if(remain > k){
                continue;
            }
            if(outOfBounds(nx, ny, n, m)){
                continue;
            }
            sb.append(dir.charAt(i));
            x = nx;
            y = ny;
            break;
        }
    }
  

  d부터 시작해서 해당 방향으로 갈 수 있는지 체크를 하고, 이동을 해버리면 자연스럽게 정답을 찾을 수 있다.

• 경로를 찾을 수 없는 경우는 두 가지이다.

  1. 경로까지 갈 수 있는 최단 거리가 k보다 큰 경우
  2. 최단 거리와 k가 둘 다 짝수이거나 홀수가 아닌 경우

📖 다른 풀이

dfs로도 풀 수는 있다. 위의 greedy한 풀이와 같이 그 다음 방향으로 갈 때 범위를 벗어나는 것과 남은 거리가 남은 이동 횟수보다 많이 남은 경우에는 강제로 return을 시켜버리고, 정답이 나온 경우에는 다른 모든 재귀호출을 return 시켜버리는 방법으로 구현이 가능하다.

📖 전체 코드

class Solution {
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        StringBuilder sb = new StringBuilder();
        String dir = "dlru";
        int[] dirx = {1, 0, 0, -1};
        int[] diry = {0, -1, 1, 0};
        
        int dist = Math.abs(x-r) + Math.abs(y-c);
        if(dist % 2 != k % 2 || dist > k){
            return "impossible";
        }
        
        while(k-- > 0){
            for(int i = 0; i < 4; i++){
                int nx = x + dirx[i];
                int ny = y + diry[i];
                int remain = Math.abs(nx - r) + Math.abs(ny - c);
                
                if(remain > k){
                    continue;
                }
                if(outOfBounds(nx, ny, n, m)){
                    continue;
                }
                sb.append(dir.charAt(i));
                x = nx;
                y = ny;
                break;
            }
        }
        return sb.toString();
    }
    boolean outOfBounds(int x, int y, int n, int m){
        if(1 <= x && x <= n && 1 <= y && y <= m){
            return false;
        }
        return true;
    }
}