미로 탈출 명령어
프로그래머스 미로 탈출 명령어 풀이
문제설명
n
x m
격자 미로가 주어집니다. 당신은 미로의 (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 합니다.
단, 미로를 탈출하는 조건이 세 가지 있습니다.
- 격자의 바깥으로는 나갈 수 없습니다.
- (x, y)에서 (r, c)까지 이동하는 거리가 총
k
여야 합니다. 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. - 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.
이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.
- l: 왼쪽으로 한 칸 이동
- r: 오른쪽으로 한 칸 이동
- u: 위쪽으로 한 칸 이동
- d: 아래쪽으로 한 칸 이동
제한사항
우선순위큐를 사용하여, Path가 작은 순으로 확인하면 10초이내에는 문제를 풀 수 있다고 생각하여, 문제를 해결했다. 50 * 50 * 2500 * log(2500 * 2500) 이므로 약 10^9 정도이다.
문제를 풀고나서 다른 사람의 코드를 참고해보니, O(K)으로 해결하는 코드가 있었다.
- 현재위치와 목적지까지의 거리가 ≤ K 이하라면, 이동이 가능하다.
- dlru 순으로 다음위치, 목적지까지의 거리를 검사하여 K이하라면 이동시킨다.
- d가 가능하면 d로 이동시킨다. (다음 순서도 마찬가지) 이런 식으로 계산하면 경로를 찾을 수 있다.
- 만약, 경로가 없는 경우는 마지막 이동 때 움직이지 못하는 경우 즉, dlru로 모두 움직여도 k의 값과 같지 않는 경우(k == 0)에는 impossible을 반환한다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}
This post is licensed under CC BY 4.0 by the author.