미로 탈출 명령어 (Kakao)

문제

미로 (x,y) 에서 시작하여 (r,c)로 이동해서 탈출해야 한다
대신
1. 총 이동거리가 k이여야 함 (시작좌표, 끝좌표 포함해서 같은 격자 밟아도 됨)
2. 미로 탈출 경로를 문자열로 나타냈을 때 문자열이 사전순으로 가장 빠른 경로로 탈출해야 함
이동경로는 l,r,u,d로 표현

우선순위는 d,l,r,u 순으로 된다

풀이

시간초과 코드

#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
char map[50][50];
int K;
int endx, endy;
int M,N;
// d l r u 순으로 
int _x[4] = {1, 0,0,-1};
int _y[4] = {0,-1, 1,0};
char alpha[4] = {'d','l','r','u'};
string ans = "";
string tmp = "";
void dfs(int x, int y, int t){
    
    if(t == K){
        if(x == endx && y == endy){ // 같은 위치 도착
            if(tmp.empty()){
                tmp = ans;
                
            }
            return;
        }
    }else if(t < K){
        for(int i=0;i<4;i++){
            int xx = _x[i] + x;
            int yy = _y[i] + y;
            if(xx >=0 && xx<N && yy>=0&& yy<M){ // 갈 수 있는지 여부 파악 
                ans += alpha[i];
                dfs(xx,yy,t+1);
                ans.pop_back();
            }
        }
    }
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    N = n;
    M = m;
    int sum = abs(x-r)+ abs(y-c);
    if(sum%2 != k%2){
        return "impossible";
    }
    map[x-1][y-1] = 1;
    map[r-1][c-1] = 2;
    endx = r-1;
    endy = c-1;
    
    K = k;
    dfs(x-1, y-1,0);
    return tmp;
    

조건 하나 더 추가한 코드

#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
char map[50][50];
int K;
int endx, endy;
int M,N;
// d l r u 순으로 
int _x[4] = {1, 0,0,-1};
int _y[4] = {0,-1, 1,0};
char alpha[4] = {'d','l','r','u'};
string ans = "";
string tmp = "";
void dfs(int x, int y, int t){
    if(!tmp.empty()){
        return;
    }
    
    if(K-t == abs(endx-x)+abs(endy-y)){ // 남는 이동수 딱 맞음 
        int tmpx = endx - x; // 양수면 아래, 음수면 위
        int tmpy = endy - y; // 양수면 오른쪽, 음수면 왼쪽
        
        if(tmpx >0){ //아래
            for(int i=0;i<tmpx;i++){
                ans+='d';
            }
        }
        
        if(tmpy < 0){ // 왼
            for(int i=tmpy;i<0;i++){
                ans+='l';
            }
        }
        
        if(tmpy >0){ // 오
             for(int i=0;i<tmpy;i++){
                ans+='r';
            }
        }
        
        if(tmpx< 0){ // 위
            for(int i=tmpx;i<0;i++){
                ans+='u';
            }
        }
        tmp = ans;
    }
    if(t == K){
        if(x == endx && y == endy){ // 같은 위치 도착
            
            tmp = ans;
                
            return;
        }
    }else if(t < K){
        for(int i=0;i<4;i++){
            int xx = _x[i] + x;
            int yy = _y[i] + y;
            if(xx >=0 && xx<N && yy>=0&& yy<M){ // 갈 수 있는지 여부 파악 
                ans += alpha[i];
                dfs(xx,yy,t+1);
                ans.pop_back();
            }
        }
    }
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    N = n;
    M = m;
    int sum = abs(x-r)+ abs(y-c);
    if(sum%2 != k%2){
        return "impossible";
    }
    map[x-1][y-1] = 1;
    map[r-1][c-1] = 2;
    endx = r-1;
    endy = c-1;
    
    K = k;
    dfs(x-1, y-1,0);
    return tmp;
    
}