Lv 3. 미로 탈출 명령어

 

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

프로그래머스

 

 

 

📌 자바(Java)로 푸는 미로 탈출 명령어 문제 - 최적화 과정 🚀

 

🔎 문제 개요

 

프로그래머스 - 미로 탈출 명령어 문제입니다.

주어진 N x M 크기의 미로에서 출발지(x, y)에서 도착지(r, c)까지 정확히 k번 이동하여 도달하는 가장 빠른 경로를 찾는 문제입니다.

단, 사전순("d" → "l" → "r" → "u")으로 가장 빠른 경로를 찾아야 합니다.

 

---

💡 예제 입력

int n = 3, m = 4;
int x = 2, y = 3, r = 3, c = 1;
int k = 5;

💡 예제 출력

"dllrl"

➡ 5번 이동하여 도착하며, 가능한 경로 중 사전순으로 가장 빠른 경로를 출력

 

---

🛠 알고리즘 접근 방식

 

이 문제를 해결하기 위해 DFS(깊이 우선 탐색) + 백트래킹을 활용합니다.

 

✏️ 주요 고려 사항

 

✔ 출발지 → 도착지까지의 최소 거리(minStep)를 계산

✔ 최소 거리보다 k가 작으면 도달 불가능 (impossible)

✔ 추가 이동(k - minStep)이 남아있다면, 남은 횟수가 짝수여야 도달 가능

✔ 사전순(d → l → r → u)으로 탐색하여 가장 빠른 경로를 찾음

✔ 백트래킹을 사용하여 불필요한 탐색을 줄이고 빠른 종료 가능

 

---

🔹 DFS + 백트래킹 풀이 (최적화 버전)

import java.util.*;

class Solution {
    
    int[][] dir = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};  // d, l, r, u 순
    char[] moveChar = {'d', 'l', 'r', 'u'};
    int K, N, M;
    String answer;  // 가장 빠른 경로 저장

    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        char[] route = new char[k];
        K = k;
        N = n;
        M = m;
        answer = null;  // 아직 정답이 없음

        int minStep = Math.abs(x - r) + Math.abs(y - c);
        if (minStep > K || (K - minStep) % 2 != 0)
            return "impossible";

        DFS(x, y, r, c, 0, route);
        
        return answer == null ? "impossible" : answer;
    }

    private boolean DFS(int sx, int sy, int r, int c, int depth, char[] route) {
        if (answer != null) return true;  // 이미 정답을 찾았으면 더 이상 탐색 X

        if (depth + Math.abs(sx - r) + Math.abs(sy - c) > K) return false;  // 백트래킹 (도착 불가능하면 중단)
        
        if (depth == K) {
            if (sx == r && sy == c) {
                answer = new String(route);  // 가장 빠른 경로 저장
                return true;  // 정답 찾았으므로 종료
            }
            return false;
        }
        
        for (int d = 0; d < 4; d++) {
            int nowX = sx + dir[d][0];
            int nowY = sy + dir[d][1];

            if (nowX < 1 || nowX > N || nowY < 1 || nowY > M)
                continue;

            route[depth] = moveChar[d];
            if (DFS(nowX, nowY, r, c, depth + 1, route)) return true;  // 정답을 찾았으면 종료
        }
        return false;
    }
}

 

 

---

🔍 코드 설명

 

📌 1. 이동 가능 여부 검사

int minStep = Math.abs(x - r) + Math.abs(y - c);
if (minStep > K || (K - minStep) % 2 != 0)
    return "impossible";

• 출발지 → 도착지까지 최소 거리(minStep) 계산

• 이 최소 거리보다 k가 작으면 도달 불가능

• 남은 이동 횟수(k - minStep)가 홀수이면 도달 불가능

 

---

📌 2. DFS + 백트래킹 탐색

private boolean DFS(int sx, int sy, int r, int c, int depth, char[] route) {
    if (answer != null) return true;  // 이미 정답을 찾았으면 탐색 종료

    if (depth + Math.abs(sx - r) + Math.abs(sy - c) > K) return false;  // 백트래킹 (불필요한 탐색 차단)
    
    if (depth == K) {
        if (sx == r && sy == c) {
            answer = new String(route);  // 가장 빠른 경로 저장
            return true;
        }
        return false;
    }

    for (int d = 0; d < 4; d++) {
        int nowX = sx + dir[d][0];
        int nowY = sy + dir[d][1];

        if (nowX < 1 || nowX > N || nowY < 1 || nowY > M)
            continue;

        route[depth] = moveChar[d];
        if (DFS(nowX, nowY, r, c, depth + 1, route)) return true;  // 정답 찾으면 종료
    }
    return false;
}

✔ 백트래킹을 적용하여 불필요한 탐색을 차단

✔ DFS 탐색 순서를 "d" → "l" → "r" → "u"로 유지하여 사전순 경로 탐색

✔ 정답을 찾으면 즉시 종료하여 최적화

 

---

🏆 정리

 

✅ 핵심 포인트

 

✔ DFS + 백트래킹을 활용하여 사전순 탐색 최적화

✔ 불필요한 탐색을 줄여 빠르게 종료 가능

✔ O(4^K) 탐색이지만 백트래킹으로 크게 줄일 수 있음