[C++] 프로그래머스 - 미로 탈출 명령어

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

<풀이>

1. 미로 정보를 입력받는다.

2. 사전 순으로 가장 빠른 미로 탈출 경로를 반환한다.

 

<해법>

1. 완전탐색 X

=> 평범한 길찾기 문제라는 생각이 듭니다. 하지만 이 문제는 k가 최대 2500이므로, 완전탐색으로 풀 때 최악의 경우 O(4^2500)의 시간복잡도를 가집니다. 따라서, 완전탐색 알고리즘은 배제해야합니다.

 

2. 불가능한 경우 찾기

=> 먼저 "impossible"한 경우부터 생각해보겠습니다.

첫번째로, 출발지점에서 끝지점까지 갈 수 있는 최단거리보다 k가 작을 경우 불가능합니다. 여기서, 출발지점에서 끝지점까지 최단거리를 계산하는 방법은 매우 간단합니다. 지도 상에 장애물이 없으므로, 맨해튼 거리계산법(ㅣx - rㅣ+ ㅣy - cㅣ)를 이용해서 구할 수 있습니다. 따라서, if(최단거리 > k) answer = "impossible" 입니다.

두번째로, (k - 최단거리) % 2 == 1 일 때 불가능합니다. 이유는 k번을 채우기 위해서는 어디선가 왔다갔다를 해야하기 때문입니다. 단순히 k번을 이용한 거리를 구하라고 한다면, 출발지점에서 끝지점까지 간 후 끝지점에서 바로 옆칸으로 왔다갔다하면 구할 수 있습니다. 그런데 이 때, '왔다갔다'를 해야하므로 2번이 필요합니다. 만약 도착지점에서 k가 1이라면 불가능합니다. 따라서, if((k - 최단거리) % 2 == 1) answer = "impossible" 입니다.

 

3. 사전순으로 가장 빠른 경로 찾기

=> 위 경우를 제외하고서는 k번 이동하여 출발지점부터 끝지점까지 갈 수 있습니다. 이제 사전순으로 가장 빠른 경로를 찾아야합니다. 사전순으로 가장 빠르려면, 앞자리가 가장 빨라야합니다. 이 말은 'd(아래)로 갈 수 있으면, d로 가는게 가장 좋다.' 입니다. 또, 'd -> l -> r -> u 순으로 갈 수있는 곳을 탐색해서 간다.' 가 됩니다. 

그렇다면 이제 해당 방향으로 가도 되는지 안되는지 판단하는 일만 남았습니다. 해당 방향으로 가도 되려면, 먼저 맵을 벗어나면 안됩니다. 그리고 또 한가지는 위에 "impossible"한 경우가 아니면 됩니다. 이 말은 다음 위치에서 최단거리 <= 남은 k 면 된다는 뜻입니다. 이렇게 하면 greedy하게 사전순으로 가장 빠른 방향으로 이동하며 정답을 구할 수 있습니다.

 

#include <string>
#include <vector>
 
using namespace std;
 
char d[] = { 'd', 'l', 'r', 'u' };
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,-1,1,0 };
 
bool isInner(int x, int y, int n, int m) {
    if (x <= 0 || y <= 0 || x > n || y > m) return false;
    return true;
}
 
string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
 
    int shortest = abs(x - r) + abs(y - c);
    if (shortest > k || (k - shortest) % 2) answer = "impossible";
    else {
        while (k--) {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (!isInner(nx, ny, n, m)) continue;
                int nshortest = abs(nx - r) + abs(ny - c);
                if (nshortest > k) continue;
                x = nx, y = ny;
                answer += d[i];
                break;
            }
        }
    }
 
    return answer;
}

 

Greedy 알고리즘에 대해 알아볼 수 있었습니다.