[Programmers] 미로 탈출 명령어(LV.3)

풀이 소요시간 : 40분 초과(실패)

일단 Lv3 치고는 문제가 무난했다. 다만 일반적인 BFS 알고리즘으로 최단경로를 구하면 절대로 풀 수 없는 문제다. DFS 로 백트래킹을 구현해야 풀 수 있는 문제였다.

백트래킹으로 가지치기를 해야 하는 경우는 두 가지가 있다.

1. 현재 좌표에서 목표 좌표까지의 거리가 남은 이동횟수보다 먼 경우

이 경우는 남은 이동횟수를 다 소모해도 어차피 목적지까지는 도달 불가능하다. 따라서 가지치기 해준다.

2. 남은 이동횟수 - 목표 좌표까지의 거리의 값이 홀수인 경우'

목표 좌표까지의 최단 거리를 제외하고 남은 이동 횟수를 모두 써서 목표 좌표에 도달하려면 무조건 남은 이동횟수가 짝수여야 한다. 홀수인 경우는 가지치기 해준다.

이렇게 백트래킹을 구현하고

3. d -> l -> r -> u 순으로 탐색을 진행한다.

이는 사전순 가장 빠른 명령어를 요구하기 때문이다. 마지막으로

4. 첫번째 요구사항을 만족하는 값이 들어오면 이는 최적값이므로 탐색을 종료한다.

3번 요구사항에 맞게 탐색을 진행하는 경우 처음으로 요구사항을 만족하는 단어가 문제의 정답이 된다. 따라서 flag 라는 변수를 이용하여 탐색을 중단할 수 있었다. 이는 백트래킹 중단하는 다른 문제에도 활용할 수 있는 포맷이다.

전체코드

#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int X, Y; //출발 지점
int R, C; //도착 지점
int N, M; //세로 가로
int K;    //거리

int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, -1, 1, 0};
vector<string> Vector;
bool flag = true;

/*

1. [도착 지점 까지의 거리]가 남은 이동횟수보다 큰 경우 [X]
2. [남은 이동횟수 - 도착 지점까지의 거리] 가 홀수인 경우 [X] 
3. d -> l -> r -> u 순으로 DFS 탐색

*/


void Dfs(int x, int y, int time, string str) {
    
    if(flag == true) {
    
        if(time == K)
        {
            if(x == R && y == C)
            {
                Vector.push_back(str);
                flag = false;
            }
            return;
        } 
    
        int Dist = abs(x - R) + abs(y - C); // 현 시점 도착지점까지의 거리
        int Left_Time = K - time;
    
        if(Left_Time < Dist) return;
        if((Left_Time - Dist) % 2 == 1) return;
    
    
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
        
            if(nx <= 0 || ny <= 0 || nx > N || ny > M) continue;
        
            if(i == 0) 
            {
                Dfs(nx, ny, time + 1, str + "d");
            }
            else if(i == 1)
            {
                Dfs(nx, ny, time + 1, str + "l");
            }
            else if(i == 2)
            {
                Dfs(nx, ny, time + 1, str + "r");
            }
            else if(i == 3)
            {
                Dfs(nx, ny, time + 1, str + "u");
            }
        }
    }
}


string solution(int n, int m, int x, int y, int r, int c, int k) {
    
    N = n; M = m;
    X = x; Y = y;
    R = r; C = c; K = k; 
    //전역 변수 세팅
    
    string str = "";
    Dfs(X, Y, 0, str);
    //탐색
    
    fin:
    if(Vector.empty() == true) return "impossible";
    return Vector[0];
}