카카오 블라인드 채용 2023 미로 탈출 명령어 c++ [사전 순]

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

 

문제의 핵심 아이디어는 

 

"사전 순"

"맨하튼 거리" 이다.

 

맨허튼 거리란?

 좌표계에서 (x1,y1) 에서 (x2,y2)로 이동할때, 최단거리는 무조건 |x1-x2| + |y1-y2|라는 내용이다.

 

이 문제는, "장애물" 과 같은 상황이 없다. 따라서 최단거리를 별도의 알고리즘으로 찾을 필요가 없이, 맨허튼 거리로 찾으면 된다. 

 

 

 

사전순이란 결국, 앞에 있는 문자가 사전순으로 높다면, 뒤에서 아무리 높아봤자 후순위로 밀리게 된다.

따라서 남은 이동 거리 > 최단 거리 일 시, 도착점 신경쓰지 않고 가능한 사전순으로 이동하다가, 최단 거리 == 이동거리가 되면 해당 지점부터 최단거리로 도착점에 도착하면 된다. (앞부분이 사전순으로 가장 높은 것이 최고의 사전순을 가진다!)

#include <string>
#include <vector>
#include<iostream>
using namespace std;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
char dir[4]={'d','l','r','u'};
 // d -> l ->r -> u    dfs로 d만 n번 -> d n-1번, l 1번,.....

int abs(int a){
    if(a<0)return -a;
    else return a;
}

int getManDist(int x1,int y1, int x2, int y2){
    return abs(x1-x2)+abs(y1-y2);
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    int man_dist=getManDist(x,y,r,c);
    if(man_dist%2 != k%2||man_dist>k)return "impossible";
    int n_x=x,n_y=y,cnt=0; 
    //남은 이동 거리 > 최단 거리 일 시, 도착점 신경쓰지 않고 가능한 사전순으로 이동
    while(cnt< (k-getManDist(n_x,n_y,r,c)) ) {
        cnt++;
        for(int i=0;i<4;i++){
            if(0>=n_x+dx[i]||n_x+dx[i]>n||0>=n_y+dy[i]||n_y+dy[i]>m)continue;// 불가능
            n_x+=dx[i];
            n_y+=dy[i];
            answer+=dir[i];
            break;
        }
    }
    //남은 거리는 최단거리로 도착점까지 이동한다.
    while(r>n_x){
        n_x++;
        answer+='d';
    }
    while(c<n_y){
        n_y--;
        answer+='l';
    }
      while(c>n_y){
        n_y++;
        answer+='r';
    }
    while(r<n_x){
        n_x--;
        answer+='u';
    }
    return answer;
}