미로 탈출 명령어

2025-01-14

#JAVA#프로그래머스

문제 링크

문제 풀이 시간 : 2시간

문제 풀이 :

처음에는 bfs, dfs로 경로 탐색하면 되는거 아닌가?

라고 생각하고 단순하게 풀었다.

나는 dfs로 d → l → r → u 순으로 탐색하면서 k번의 이동으로 목적지 까지 가면 무조건 사전순으로 빠른 경로가 나온다는 생각으로 문제를 풀었다.

근데 그렇게 하면 당연하게? 시간초과가 난다.

그래서 생각했던 방법이 일단 dfs로 최단 경로를 구하고 남은 이동 횟수 만큼 위아래 혹은 좌우 이동을 하면서 경로를 채우는 방식을 생각해서 아래와 같은 코드를 짰다..

초기 코드

Java

class Solution {
    public boolean[][] visited;
    public int[][] dir = {{1,0},{0,-1},{0,1},{-1,0}};
    public String[] dir_char = {"d","l","r","u"};
    public int dest_x, dest_y, bx, by;
    public String rt;
    public boolean flag = false;
    
    public void find(int x, int y, String route){ //최단 경로 계산 함수
        if(x == dest_x && y == dest_y){
            rt = route;
            flag = true;
            return;
        }
        for(int i=0;i<4;i++){
            int tx = x+dir[i][0];
            int ty = y+dir[i][1];
            
            if(visited[tx][ty] || !check(tx,ty) || flag){
                continue;
            }
            visited[tx][ty] = true;
            find(tx,ty,route+dir_char[i]);
            visited[tx][ty] = false;
        }
        
    }
    
    public boolean check(int x, int y){
        if(x<1||y<1||x>bx||y>by){
            return false;
        }
        return true;
    }
    
    public void rest(int x, int y, String route, int k){ // 남은 경로 이동 함수
        if(x<bx){
            while(route.length()!=k){ //아래로 이동할 수 있다면 du가 사전 순으로 가장 빠름
                route+="du";
            }
        }
        else if(y>1){
            while(route.length()!=k){ //왼쪽으로 이동할 수 있다면 lr이 사전 순으로 가장 빠름
                route+="lr";
            }
        }
        else if(y<by){
            while(route.length()!=k){
                route+="rl";
            }
        }
        else{
            while(route.length()!=k){
                route+="ud";
            }
        }
        rt = route;
    }
    
    public String realign(String route, int x, int y, int r, int c){ // 재정렬 함수
        int d=0,l=0,r=0,u=0;
        for(int i=0;i<route.length();i++){
            if(route.charAt(i)=='d')
                d++;
            else if(route.charAt(i)=='l')
                l++;
            else if(route.charAt(i)=='r')
                r++;
            else if(route.charAt(i)=='u')
                u++;
        }
        
        String ans = "";
        int t1 = d;
        int t2 = bx - x;
        for(int i=0;i<Math.min(t1,t2);i++){
            ans+="d";
            d--;
            x++;
        }
        
        t1 = l;
        t2 = y-1;
        for(int i=0;i<Math.min(t1,t2);i++){
            ans+="l";
            l--;
            y--;
        }
        
    }
    
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        String answer = "";
        bx = n;
        by = m;
        dest_x = r;
        dest_y = c;
        visited = new boolean[n+2][m+2];
        visited[x][y] = true;
        
        find(x,y,"");
        
        if(rt.length()>k||(k-rt.length())%2==1){
            return "impossible";
        }
        
        rest(r,c,rt,k);
        answer = rt;
        
        return answer;
    }
}

하지만 위와 같은 코드에서는 메모리 초과가 나서 제대로 동작하지 않는다.

그래서 결국 다른 사람의 풀이를 참고해서 문제를 다시 풀어보았다.

일단 내가 생각했던 풀이와 상당히 유사했지만

코드를 작성하는 방법에 큰 차이가 있었다.

일단 현재 위치에서 목적지 까지의 경로의 거리를 계산한다.

Java

int diff = Math.abs(x-r) + Math.abs(y-c); //최단 경로 거리 계산
k -= diff; //이동 횟수에서 차감

그 후, 남은 이동 횟수가 0보다 작거나 2의 배수가 아니라면 impossible을 리턴한다.

0보다 작다면 최단 경로로도 이동할 수 없다는 말이고,

2의 배수가 아니라면 아래위, 좌우 이동으로 남은 이동거리를 채울 수 없기 때문이다.

Java

if(k<0 || k%2!=0){
	return "impossible";
}

그 후, 최단 경로로 이동한 경로를 구해서 각 이동 횟수를 계산한다.

Java

if(x>r){ //현재 위치의 x좌표가 목적지의 x좌표보다 아래에 있다면 위로 이동
	up+=x-r;
}
else{ //위에 있다면 아래로 이동
	down+=r-x;
}
if(y>c){ // 현재 위치의 y좌표가 목적지의 y좌표보다 오른쪽에 있다면 왼쪽 이동
	left += y-c;
}
else{ //왼쪽에 있다면 오른쪽 이동
	right += c-y;
}

d가 사전순으로 가장 빠르기 때문에 d를 가장 먼저 사용해주기 위해 d에 대한 계산을 한다.

Java

answer.append("d".repeat(down)); //아래로 이동한 횟수만큼 경로에 추가
int extra_down = Math.min(k/2,n-(x+down)); //남은 이동거리의 반, 아래로 이동할 수 있는 최대 거리 중 작은 값 선택
answer.append("d".repeat(extra_down)); //추가 이동거리 만큼 경로에 추가
up += extra_down; // 아래로 추가로 이동한만큼 위로 이동 횟수 추가
k-=2*extra_down; //남은 이동거리 계산

Java

answer.append("l".repeat(left)); //왼쪽으로 이동한 횟수만큼 경로 추가
int extra_left = Math.min(k/2,y-left-1); //남은 이동거리의 반, 추가로 왼쪽 이동할 수 있는 최대 거리 중 작은 값 선택
answer.append("l".repeat(extra_left)); //추가 이동거리 만큼 경로에 추가
right += extra_left; // 오른쪽 추가 이동거리 횟수 추가
k-=2*extra_left; //남은 이동거리 계산

만약 위 과정을 모두 거치고도 이동거리가 남았다면

현재 위치가 가장 왼쪽 아래이므로 ud 혹은 rl 로 이동을 할 수 있다.

하지만 rl이 사전순으로 더 빠르므로 rl을 남은 이동거리만큼 반복해준다.

그 후, 오른쪽, 위쪽 이동을 처리해주면 된다.

Java

answer.append("rl".repeat(k/2)); //남은 이동거리 사용
        
answer.append("r".repeat(right)); //오른쪽 이동 처리
answer.append("u".repeat(up)); //위쪽 이동 처리

최종 코드

Java

import java.util.*;
import java.io.*;

class Solution {
    public String solution(int n, int m, int x, int y, int r, int c, int k) {
        StringBuilder answer = new StringBuilder();
        int down = 0, left = 0, up = 0, right = 0;
        
        int diff = Math.abs(x-r) + Math.abs(y-c);
        k -= diff;
        
        if(k<0 || k%2!=0){
            return "impossible";
        }
        
        if(x>r){
            up+=x-r;
        }
        else{
            down+=r-x;
        }
        
        if(y>c){
            left += y-c;
        }
        else{
            right += c-y;
        }
        
        answer.append("d".repeat(down));
        int extra_down = Math.min(k/2,n-(x+down));
        answer.append("d".repeat(extra_down));
        up += extra_down;
        k-=2*extra_down;
        
        answer.append("l".repeat(left));
        int extra_left = Math.min(k/2,y-left-1);
        answer.append("l".repeat(extra_left));
        right += extra_left;
        k-=2*extra_left;
        
        answer.append("rl".repeat(k/2));
        
        answer.append("r".repeat(right));
        answer.append("u".repeat(up));
        
        
        return answer.toString();
    }
}