프로그래머스 미로 탈출 명령어 - C++ 풀이

---

 

1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부
2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc)가 하나라도 있는가
3. 이동방향에 대한 우선순위는 d, l, r, u이다.

 

1. dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 도달할 수 있는지 여부

 dp(r, c, k)를 위와 같이 정의하자. R = C = 50, K = 2500이므로 구해야 하는 상태값의 개수는 50*50*2500개. 제한 시간 내에 모두 구하기 충분하다. 기저 사례는 k=0인 경우로 이때 위치한 칸이 도착지점인지 판단하면 된다.

 

2. dp(r, c, k): dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc)가 하나라도 있는가

 dp(r, c, k)는 다음과 같이 계산할 수 있다. "dp(nr, nc, k-1) = 1인 인접한 칸 (nr, nc)가 하나라도 있는가". 이 말은 곧 "탈출이 가능한 인접한 칸이 존재하는가"와 같다. 탈출이 보장된 인접한 칸이 존재한다면 해당 칸으로 이동하자. 이동 후에는 또 인접한 칸에 대해 탈출이 보장된 칸을 찾아 그곳으로 이동하는 것을 반복하면 된다.

 

3. 이동방향에 대한 우선순위는 d, l, r, u이다.

 탈출 경로는 여러 개가 될 수 있다. 그 중 사전순으로 가장 빠른 것을 골라야 한다. 인접한 칸(상하좌우)을 하나씩 고려할 때, 사전순으로 우선순위를 매겨서 탐색해야 한다. 사전순은 d-l-r-u 순이다.

 

---

#include <string>
#include <vector>
#include <string.h>
#include <iostream>

using namespace std;
const int MAX_N = 51;
const int MAX_K = 2'501;

int N, M, SR, SC, ER, EC, K;
int cache[MAX_N][MAX_N][MAX_K];
char dir[] = {'d', 'l', 'r', 'u'};
int dr[] = {1, 0, 0, -1};
int dc[] = {0, -1, 1, 0};
char answer[MAX_K];

// dp(r, c, k): (r,c)에서 정확히 k번의 이동으로 도착지점에 갈 수 있는가
int dp(int r, int c, int k) {
    if (k == 0) {
        // 도착 지점 도달했는지 여부
        return (r == ER && c == EC);
    }
    
    int& ret = cache[r][c][k];
    if (ret != -1) return ret;
    
    ret = 0;
    if (k > 0) {
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (nr < 1 || nr > N || nc < 1 || nc > M) continue;
            
            // 다음 칸으로 이동
            ret = max(ret, dp(nr, nc, k-1));
        }
    }
    
    return ret;
}

void track(int r, int c, int k, string& route) {
    if (k == 0) return;
    
    // d-l-r-u 순으로 탐색
    for (int i=0; i<4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if (nr < 1 || nr > N || nc < 1 || nc > M) continue;
        
        if (dp(nr, nc, k-1)) {          // (nr, nc)로 가서 탈출이 가능하다면
            route[K-k] = dir[i];        // (nr, nc)로 이동
            track(nr, nc, k-1, route);  // 이어서 다음 경로 찾기
            return;   
        }
    }
}

string calcRoute() {
    string route(K, ' ');
    
    track(SR, SC, K, route);
    
    return route;
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    N = n; M = m; SR = x; SC = y; ER = r; EC = c; K = k;
    
    memset(cache, -1, sizeof(cache));
    answer = dp(SR, SC, K) ? calcRoute() : "impossible";
    
    return answer;
}