미로 탈출 명령어

• 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/150365?gad_source=1&gad_campaignid=22366107751&gbraid=0AAAAAC_c4nDUvt0gMNLTRhBBrsmG3RwVZ&gclid=Cj0KCQiApL7KBhC7ARIsAD2Xq3AU-b-d-xBRJNdBUE3otgg5eL3P94gf7D8U7Eb2XDYXEqPN9Jd9S8EaAogvEALw_wcB

• 푼 방법

이 문제 풀이의 핵심은 딱 5가지임

1. 어떠한 지점을 재 방문이 가능하기 때문에, 방문 배열은 그냥 H * W 크기의 배열이 아닌 K * H * W 크기로 선언해준다.
2. 움직이는 방향의 순서를 d, l, r, u 순으로 움직인다. (즉, 사전 순으로)
3. BFS 가 아닌 DFS 를 사용하여, 1번에서 정한 순으로 움직였을 때, 처음으로 목적지에 도착한 경우 사전 순으로 가장 빠른 경우가 되도록한다.
4. 다른 격자로 이동할 때마다, 현재 해당 격자로 이동하기 위해 어떤 방향으로 움직였는지 기록해둔다.
5. 목적지에 다다랐을 때, 기록한 방향 정보들을 가지고 역으로 어떻게 움직여서 목적지까지 왔는지 추적한다.

위 5가지를 지키면 쉽게 풀 수 있음

• 시간 복잡도

O(K * H * W)

• Code

import java.util.*;

class Solution {
    
    public int H;
    public int W;
    public int K;
    public int r1;
    public int c1;
    public int r2;
    public int c2;
    public boolean[][][] visited;
    public int[][][] track;
    public int[] dx = {0, -1, 1, 0};
    public int[] dy = {1, 0, 0, -1};
    public String answer = "impossible";
    
    public boolean outOfRange(int y, int x) {
        return y < 0 || y >= H || x < 0 || x >= W;
    }
    
    public void dfs(int y, int x, int count, int preDir) {
        if (!answer.equals("impossible")) {
            return;
        }
        
        if (visited[count][y][x]) {
            return;
        }
        
        visited[count][y][x] = true;
        track[count][y][x] = preDir;
        
        if (count == K) {
            if (y == r2 && x == c2) {
                answer = tracking();
            }
            
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            int nCount = count + 1;
            
            if (outOfRange(ny, nx)) {
                continue;
            }
            
            dfs(ny, nx, nCount, i);
        }
    }
    
    public String tracking() {
        StringBuilder ans = new StringBuilder();
        int count = K;
        int r = r2;
        int c = c2;
        
        while (count != 0) {
            int dir = track[count][r][c];
            
            if (dir == 0) {
                r--;
                ans.append("d");
            } else if (dir == 1) {
                c++;
                ans.append("l");
            } else if (dir == 2) {
                c--;
                ans.append("r");
            } else {
                r++;
                ans.append("u");
            }
            
            count--;
        }
        
        return ans.reverse().toString();
    }
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        this.H = n;
        this.W = m;
        this.K = k;
        this.r1 = x - 1;
        this.c1 = y - 1;
        this.r2 = r - 1;
        this.c2 = c - 1;
        
        visited = new boolean[K + 1][H][W];
        track = new int[K + 1][H][W];
        dfs(r1, c1, 0, -1);
        return answer;
    }
    
}