미로 탈출 명령어 [Lv.3]

프로그래머스

 

(n, m)크기의 격자 미로에서 (x,y) -> (r, c)까지 k번 이동해서 도착하는 경로를 출력하는 문제입니다.

경로를 출력할때 이동하는 방향 왼쪽, 오른쪽, 위, 아래는 각각 l, r, u, d를 출력해야하며

각 문자열을 알파뱃순서로 정렬했을때 가장 앞에오는 것을 출력해야 합니다.

 

풀이방법

우선 DFS로 풀면 될것같습니다.

또한 다음 level로 들어갈 때 알파뱃 순서대로 (d, l, r, u) 들어가면

우선순위가 가장 높은 문자열을 가장 먼저 찾을 수 있을겁니다.

예시)

DFS(pos + Pos{1, 0}, str + 'd');
DFS(pos + Pos{0, -1}, str + 'l');
DFS(pos + Pos{0, 1}, str + 'r');
DFS(pos + Pos{-1, 0}, str + 'u');

 

속도 최적화를 안하면 속도 문제 때문에 풀 수 없을 것  같습니다.

1. 현재 남은 이동 거리가 도착지점까지의 거리보다 작다면 return

2. 이동 가능거리가 출발지점 -> 도착지점까지 거리보다 작다면 impossible 출력

3. 이동가능거리 - 출발지점->도착지점 거리가 홀수면 impossible (도착했는데 이동 가능거리 1이 남았다면 불가능)

 

정답 코드

struct Pos
{
    int x;
    int y;
    
    Pos operator +(Pos other)
    {
        Pos r;
        r.x = x + other.x;
        r.y = y + other.y;
        return r;
    }
    
    bool operator == (Pos other)
    {
        return x == other.x && y == other.y;
    }
    
    int Distance(Pos other)
    {
       return abs(other.x - x) + abs(other.y - y);
    }
};

위치값 관리용 struct

 

int N, M, K;
Pos dst;
string answer;

전역변수

 

void DFS(Pos pos, string str)
{
    if (answer.size() > 0 || 
        pos.Distance(dst) > K - str.size() ||
        pos.x >= N || pos.x < 0 || 
        pos.y >= M || pos.y < 0)
        return;
    
    if (str.size() == K){
        if (pos == dst)
            answer = str;
        
        return;
    }
    
    DFS(pos + Pos{1, 0}, str + 'd');
    DFS(pos + Pos{0, -1}, str + 'l');
    DFS(pos + Pos{0, 1}, str + 'r');
    DFS(pos + Pos{-1, 0}, str + 'u');
}

answer.size() > 0 -> 정답을 이미 찾았다면 return;

pos.Distance(dst) > K - str.size() -> 남은 거리가 이동 가능거리보다 크다면 return;

범위를 벗어났다면 return;

 

string solution(int n, int m, int x, int y, int r, int c, int k) {
    N = n; M = m; K = k;
    dst = Pos{r-1, c-1};
    
    int dist = dst.Distance(Pos{x-1, y-1});
    if ((K - dist) % 2 == 0 && dist <= k) {
        DFS(Pos{x-1, y-1}, "");
    }
    else
        answer = "impossible";
    
    
    return answer;
}