[2023 KAKAO BLIND RECRUITMENT] 미로 탈출 명령어

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150365

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 bfs를 이용하여 풀 수 있습니다. 하지만 한 가지 주의할 점이 있는데, 바로 왔던 경로를 재탐색이 가능하다는 것입니다. 이렇게 되면 지난 경로도 계속 탐색하기 때문에 상,하,좌,우 4가지의 방향이 k번 만큼 이동해야 하기 때문에 O(4^k)의 시간 복잡도로 시간초과가 발생합니다. 이를 해결하기 위해선 하나의 아이디어가 필요합니다.

바로 현재 남은 이동 횟수를 체크 배열에 포함시켜서 check[y][x][남은 이동 횟수] 이렇게 3차원 배열로 설정하여 체크된 부분만 지나가는 방식입니다. 이 때 주의할 점은 이동 시 문자열이 가장 빠른 순서대로, 즉 아래(d), 왼쪽(l), 오른쪽(r), 위쪽(u) 순으로 이동해야 한다는 것입니다. 이렇게 되면 해당 위치에 가장 먼저 도착하는 값이 문자열이 가장 빠른 순이기 때문에 자연스럽게 해당 위치에서 남은 경로가 정해져 있으면 유일한 하나의 값으로 정의됩니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static String getAnswer(String str1, String str2, int k){
        for(int i=0;i<k;i++){
            // 만약 현재 문자열이 더 빠르다면 대체 후 break
            if(str1.charAt(i) < str2.charAt(i)) return str1;
            // 만약 기존 문자열이 더 빠르다면 그대로 break
            else if(str1.charAt(i) > str2.charAt(i)) break;
        }
        return str2;
    }
    
    public String solution(int n, int m, int y, int x, int r, int c, int k) {
        String answer = "";
        int[] dx = {0,-1,1,0};
        int[] dy = {1,0,0,-1};
        String[] command = {"d","l","r","u"};
        boolean[][][] check = new boolean[51][51][2501];

        // bfs
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(y,x,k,""));

        while(!queue.isEmpty()){
            Pair curr = queue.poll();

            // 이동을 k번 했다면
            if(curr.remain == 0){
                // x,y가 r,c인지 확인
                if(curr.y==r && curr.x==c){

                    // 정답에 아무것도 없을 경우 정답에 커맨드 추가
                    if(answer.equals("")) answer = curr.command;

                    // 정답이 있다면 문자열이 사전 순으로 가장 빠른 경로로 탈출
                    else answer = getAnswer(curr.command,answer,k);
                }
                continue;
            }

            // 상하좌우 이동
            for(int i=0;i<4;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                int remain = curr.remain;
                String nc = curr.command + command[i];

                if(ny<1 || ny>n || nx<1 || nx>m) continue;

                // 지난 경로가 아니라면 큐에 추가
                if(!check[ny][nx][remain]){
                    check[ny][nx][remain] = true;
                    queue.add(new Pair(ny, nx, remain-1, nc));
                }
            }
        }

        if(answer.equals("")) answer = "impossible";
        return answer;
    }
}

class Pair{
    int y;
    int x;
    int remain;
    String command;

    Pair(int y, int x, int remain, String command){
        this.y = y;
        this.x = x;
        this.remain = remain;
        this.command = command;
    }
}