[Programmers] 프로그래머스 Lv.3 미로 탈출 명령 문제풀이(C++)

이동 순서를 잘 따지면서, 남은이동거리를 잘 카운팅하는 것이 중요한 문제였음 

#include <string>
#include <vector>
 
using namespace std;
/*
<문제>
m * n 격자가 주어짐
(x, y) -> (r, c) 로 이동해야 함 / (1, 1)부터 시작
  1. 격자바깥 못감
  2. 이동거리가 총 k여야 함(시작, 끝 포함해서 같은 격자 두번 이상 방문 가능)
  3. 탈출경로를 문자열로 나타냈을 때, 사전순으로 가장 빠른 경로로 탈출
각 경로 : l, r, u, d(왼, 오, 위, 아)
불가능 한 경우, "impossible" return
 
2<=n, m<=50
시작, 끝은 같지 않음
k<=2500
 
<풀이>
d < l < r < u -> 아래, 왼쪽, 오른쪽, 위 순서대로 우선
 
impossible 경우
  1. 최소이동거리랑 k가 각각 홀수, 짝수로 같으면 가능 / 아니면 불가능
  2. k가 최소이동거리보다 작은 경우
 
if(최소이동거리 % 2 != k%2) return "impossible";
아래로 이동 / 왼쪽 이동 / 오른쪽 이동 / 위 이동
목적지 도달했는데, 이동거리가 k가 넘었으면 -> impossible
 
 * 아래로 최대한 이동 / 왼쪽 최대한 이동 / 오른쪽 한번 이동 후 부족하면 왼쪽 한번 이동(반복) / 이동거리 다 메꿨으면 오른쪽 최대한 이동 / 위로 최대한 이동
 * 남은 이동거리를 잘 카운팅해야 함
 
<시간>
왼쪽 아래로 몰아넣을 때 100번
k값에 따라 2씩 빼면서 좌우이동 -> 많아야 2500번
이동거리 다 채우고 오른쪽 위로 이동 -> 많아야 100번
 -> 무조건 가능
*/
 
int get_distance(int lr, int ud){ //절대값으로 이동거리 구해줌(가로세로합)
    if(lr<0) lr*=-1; if(ud<0) ud*=-1; 
    return lr+ud;
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
  
    
    int lr = (c-y), ud = (r-x);  //좌우 및 상하 이동해야 하는 거리(- 붙으면 오른쪽 또는 위로 가야함)
    int min = 0;
    if(lr<= 0) min+=(lr*-1); else min+=lr;
    if(ud<= 0) min+=(ud*-1); else min+=ud;
    //최소이동거리 입력 완료(= 현재로서 목적지까지 남은 이동거리)
    
    if( (min%2!=k%2) || (k<min) ) return "impossible";
    //최소이동거리와 K가 홀짝이 같고, k가 최소이동거리 이상이어야 함
 
    //x, y를 현 위치로 사용
    while(get_distance(lr, ud)<k && x<n){   //k를 계속 깎아내려갈거 -> 이동거리 채우기
            x++; k--; answer+="d"; ud = r-x; //위아래 거리조정
    }
    while(get_distance(lr, ud)<k && y>1){ //왼쪽 최대한 이동
        y--; k--; answer+="l"; lr = c-y; //좌우 거리조정; 
    }
    while(get_distance(lr, ud)<k){ //오른쪽 한번 이동 후 왼쪽 한번 이동 -> 여기서 거리조절 끝
        k-=2; answer+="rl"; lr = c-y; //좌우 거리조정; 
    }
    // get_distance(lr, ud) == k인 상태임
    
    if(ud>0){
        for(int i=0; i<ud; i++)
            answer+="d";
    }
    
    if(lr<0){
        for(int i=0; i<lr*(-1); i++)
            answer+="l";
    }
    else{
        for(int i=0; i<lr; i++)
            answer+="r";
    }
    if(ud<0){
        for(int i=0; i<ud*(-1); i++)
            answer+="u";
    }
    
    return answer;
}