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

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

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

프로그래머스

---

미로 탈출 명령어

N * M 격자 미로가 있을 때, (x, y)에서 출발해서 (r, c)까지 이동하려고 한다. 이때 아래의 규칙을 지키며 이동한다.

격자 바깥으로 나갈 수 없다.

이동하는 거리는 총 K여야 한다. 같은 격자를 2번 이상 방문해도 된다.

미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로여야 한다.

 

이동경로를 문자열로 바꾸는 것은 l -> 왼쪽, r -> 오른쪽, u -> 위쪽, d -> 아래쪽이다.

---

문제해결

BFS를 이용해서 문제를 해결했다.

 

같은 격자를 2번 이상 방문해도 되기 때문에 방문체크 배열을 3차원으로 사용하였다. 또한 이동경로를 알아야 하기 때문에 이전 이동 정보를 담은 prev 배열을 3차원으로 사용하였다.

visit[i][j][k] : (i, j) 좌표까지 k거리로 왔었으면 true

prev[i][j][k] : (i, j) 좌표까지 k거리로 왔을 때 이전 좌표와 어느 방향으로 왔는지가 저장되어 있다.

 

사전순으로 경로가 앞서야 하기 때문에 인접 노드를 계산하는 di, dj 배열을 d, l, r, u 순으로 만들었다.

 

자세한 로직은 다음과 같다.

• 큐에 시작 노드를 넣는다.
• 큐의 크기만큼 for문을 돌린다. -> 같은 거리의 노드를 처리한다.
  • 큐에서 노드를 꺼내고, 해당 노드의 인접 노드를 dist+1만큼의 거리로 오지 않았다면 방문한다. 
  • 방문 표시를 하고, 이전 노드를 기록한다.
  • 만약 인접노드가 도착 노드이고 dist+1의 값이 K라면 정답을 찾은 것이므로 정답 문자열을 만들러 간다. -> answer()
• dist가 K라면 더이상 진행하지 않는다.

---

코드

import java.util.*;
class Solution {
    static int N, M, K;
    static Tuple Start, End;
    static int[] di = {1, 0, 0, -1};
    static int[] dj = {0, -1, 1, 0};
    static class Tuple{
        int x, y;
        public Tuple(int x, int y){
            this.x = x;
            this.y = y;
        }
        int d;
        public Tuple(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }
        
    }
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        N = n; 
        M = m;
        K = k;
        Start = new Tuple(x-1, y-1);
        End = new Tuple(r-1, c-1);
        
        return BFS();
    }
    static String BFS(){
        boolean[][][] visit = new boolean[N][M][K+1];
        Tuple[][][] prev = new Tuple[N][M][K+1];
        Queue<Tuple> Q = new ArrayDeque<>();
        visit[Start.x][Start.y][0] = true;
        Q.add(new Tuple(Start.x, Start.y));
        
        int dist = 0;
        while(!Q.isEmpty()){
            int size = Q.size();
            for(int p = 0; p < size; p++){
                Tuple tp = Q.poll();
                for(int k = 0; k < 4; k++){
                    int ni = tp.x + di[k];
                    int nj = tp.y + dj[k];
                    if (ni < 0 || nj < 0 || ni >= N || nj >= M || visit[ni][nj][dist+1]) continue;
                    visit[ni][nj][dist+1] = true;
                    prev[ni][nj][dist+1] = new Tuple(tp.x, tp.y, k);
                    if(dist+1 == K && ni == End.x && nj == End.y){
                        return answer(prev);
                    }
                    Q.add(new Tuple(ni, nj));
                }
            }
            dist++;
            if(dist == K) break;
        }
        return "impossible";
    }
    static char[] dir = {'d', 'l', 'r', 'u'};
    static String answer(Tuple[][][] prev){
        StringBuffer sb = new StringBuffer();
        int dist = K;
        Tuple tp = prev[End.x][End.y][dist--];
        while(tp != null){
            sb.append(dir[tp.d]);
            tp = prev[tp.x][tp.y][dist--];
        }
        return sb.reverse().toString();
    }
}

---

결과

---