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

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

문제 접근 방식

• 보자마자 BFS 문제인걸 알았다. 완전 탐색 dfs로 풀기에는 2의 2500승이라서 안될거 같다..
• 다만 중복 방문이 가능해서 일단 방문 처리를 안하고 BFS로 했을 때는 시간 초과가 발생한다.
• 따라서 방문 처리를 하는 대신, 방문하지 않았거나 + 이미 방문했으나 이전과 거리가 다르거나 + 거리가 같으면 이전에 방문했을 때보다 현재가 사전 순이 더 빠를 때 총 3가지 경우에만 방문할 수 있도록 한다.
• 참고로 행의 값이 증가해야 down, 값이 감소하면 up이다. 처음에 x,y 그래프로 생각해서 값이 증가하면 up, 값이 감소하면 down이라고 생각했다. 근데 우리가 문제를 풀 때는 배열을 이용한다. 따라서 배열 상에서는 행의 값이 증가하면 아래로 내려옴을 유의하자!

import java.util.*;
import java.awt.*;

class Solution {
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        int dx[]={1,-1,0,0};
        int dy[]={0,0,-1,1}; // 상 하 좌 우
        char d[] = {'d','u','l','r'};
        
        String visited[][] = new String[n+1][m+1];
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x,y));
        visited[x][y]="";
        
        String min = "";
        boolean flag = false;
        
        while(!queue.isEmpty()){
            Point now = queue.poll();
            String nowS = visited[now.x][now.y];
            if(now.x==r&&now.y==c&&nowS.length()==k){
                flag=true;
                if(min.equals("")) min = nowS;
                else if(min.compareTo(nowS)>0) min = nowS;
            }
            
            if(nowS.length()<k){
                for(int i=0; i<4; i++){
                    int newX = now.x+dx[i];
                    int newY = now.y+dy[i];
                    String newS = nowS+d[i];
                    if(1<=newX&&newX<=n && 1<=newY&&newY<=m){
                        String isVisit = visited[newX][newY];
                        if(isVisit==null||isVisit.length()!=newS.length()||
                          (isVisit.length()==newS.length()&&isVisit.compareTo(newS)>0)){
                                queue.add(new Point(newX,newY));
                                visited[newX][newY]=newS;
                        }
                    }
                }
            }
        }
        return flag ? min : "impossible";
    }
}

시간 초과를 해결해서 맞추긴 했는데 테스트 시간이 너무 오래걸렸다... 통과 못할줄 알고 조마조마;;
더 최적화할 수 있는 방법이 없나 찾아봤다.

import java.util.*;

class Solution {
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        // 출발점과 도착점의 맨해튼 거리 계산
        int distance = Math.abs(r - x) + Math.abs(c - y);
        // 도달 불가능한 경우 (거리와 k의 차이가 홀수이거나, k가 거리보다 작은 경우)
        if (distance > k || (k - distance) % 2 != 0) {
            return "impossible";
        }

        // 가능한 방향과 대응하는 문자 배열
        int[] dx = {1, 0, 0, -1}; // 하, 좌, 우, 상 (사전순)
        int[] dy = {0, -1, 1, 0};
        char[] dir = {'d', 'l', 'r', 'u'};
        
        StringBuilder path = new StringBuilder();
        int remainingMoves = k;
        
        // 탐색을 시작하여 경로를 구성
        while (remainingMoves > 0) {
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                
                // 경계를 벗어나지 않으면 이동 시도
                if (newX >= 1 && newX <= n && newY >= 1 && newY <= m) {
                    // 이동 후 남은 거리 계산
                    int newDistance = Math.abs(r - newX) + Math.abs(c - newY);
                    if (newDistance <= remainingMoves - 1) { // 남은 이동 횟수 내에 도달 가능
                        path.append(dir[i]);
                        x = newX;
                        y = newY;
                        remainingMoves--;
                        break;
                    }
                }
            }
        }
        
        return path.toString();
    }
}

• 그리디적인 방법입니다. 애초에 방향을 사전순이 빠른 d,l,r,u 순으로 탐색하면 굳이 비교하지 않아도 가장 먼저 이동 횟수 k일 때 나오는 경로가 정답이 됩니다.
• 맨해튼 거리를 계산하여 이동할 수 있는지 판단후, 이동 횟수 안에 이동이 가능하면 while문을 통해 탐색합니다.
• 이때 이동할 수 없는지는 두 가지 경우로 판단합니다.

1. 맨해튼 거리가 이동 횟수 k보다 클 때
2. 이동 횟수 k - 맨해튼 거리가 홀수 일때

• 위에서 2번의 경우가 이해가 잘 안됐는데요. 제가 이해했을 때는 예를 들어 3번만의 도달할 수 있는 거리를 4번에 가야한다고 하면 4-3==1이 되고 도달할 수가 없습니다.
• 더 이동해서 도달하려면 최소 2번 이상 이동해야됩니다. (예를 들어 목적지에서 아래로 물러났다가 다시 목적지로 이동한다고 하면 d -> u 최소 2번 움직여야합니다.)
• 따라서 최소 거리와 이동 횟수 k가 홀수만큼 차이나면 도달할 수가 없어요!

이 방법으로 사용했더니 훨씬 빨라졌습니다..