미로 탈출 명령어

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

문제설명

n x m 격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동
• r: 오른쪽으로 한 칸 이동
• u: 위쪽으로 한 칸 이동
• d: 아래쪽으로 한 칸 이동

제한사항

우선순위큐를 사용하여, Path가 작은 순으로 확인하면 10초이내에는 문제를 풀 수 있다고 생각하여, 문제를 해결했다. 50 * 50 * 2500 * log(2500 * 2500) 이므로 약 10^9 정도이다.

문제를 풀고나서 다른 사람의 코드를 참고해보니, O(K)으로 해결하는 코드가 있었다.

1. 현재위치와 목적지까지의 거리가 ≤ K 이하라면, 이동이 가능하다.
2. dlru 순으로 다음위치, 목적지까지의 거리를 검사하여 K이하라면 이동시킨다.
   1. d가 가능하면 d로 이동시킨다. (다음 순서도 마찬가지) 이런 식으로 계산하면 경로를 찾을 수 있다.
3. 만약, 경로가 없는 경우는 마지막 이동 때 움직이지 못하는 경우 즉, dlru로 모두 움직여도 k의 값과 같지 않는 경우(k == 0)에는 impossible을 반환한다.

소스코드

#include <bits/stdc++.h>

#define pii pair<int, int>
using namespace std;

// 알파벳 순: dlru
char dir[4] = {'r','d','l','u'};
int dx[4] = {0,1,0,-1}; 
int dy[4] = {1,0,-1,0};

struct move{
    string path;
    int x;
    int y;
    int cnt;
};
struct compare{
    bool operator()(const struct move& a, const struct move& b){
        return a.path < b.path;
    }
};
string dp[51][51][2501]; //[x][y][k]
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string ans = "";
    priority_queue<struct move, vector<struct move>, compare> pq;
    pq.push({"", x,y,0});
    while(!pq.empty()){
        struct move cur = pq.top();
        pq.pop();
        if(cur.cnt == k && cur.x == r && cur.y == c){
            ans = cur.path;
            break;
        }
        // 중복된 연산 방지
        if(cur.cnt >= k) continue;
        if(!dp[cur.x][cur.y][cur.cnt].empty() && dp[cur.x][cur.y][cur.cnt] <= cur.path) continue;
        for(int i = 0; i<4; i++){
            int nx = cur.x + dx[i]; int ny = cur.y + dy[i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){
                string new_path=path;
                new_path.push_back(dir[i]);
                pq.push({new_path, nx, ny, cur.cnt + 1});
            }
        }
        
        
    }
    if(ans == "") ans = "impossible";
    return ans;
}