[프로그래머스] 미로 탈출 명령어 (2023 KAKAO BLIND RECRUITMENT)

프로그래머스 미로 탈출 명령어 문제입니다.

프로그래머스

문제

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

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

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

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

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

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3 x 4 격자가 있다고 가정해 보겠습니다.

....
..S.
E...

 

미로의 좌측 상단은 (1, 1)이고 우측 하단은 (3, 4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 k가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud
2. ulldd
3. rdlll
4. dllrl
5. dllud
6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

격자의 크기를 뜻하는 정수 n, m, 출발 위치를 뜻하는 정수 x, y, 탈출 지점을 뜻하는 정수 r, c, 탈출까지 이동해야 하는 거리를 뜻하는 정수 k가 매개변수로 주어집니다. 이때, 미로를 탈출하기 위한 경로를 return 하도록 solution 함수를 완성해주세요. 
단, 위 조건대로 미로를 탈출할 수 없는 경우 "impossible"을 return 해야 합니다.

알고리즘 아이디어

처음에 미로 탈출만 보고 BFS로 접근해서 풀려고 하면 시간초과가 난다.

이 문제는 Greedy로 풀어야 한다.

1. 경로가 존재하는지 판별

목표 (r, c)까지 도달하는 최소 이동 거리를 min_dist라고 하면,

int min_dist = abs(x - r) + abs(y - c);

여기서 다음 조건을 만족해야 탈출 가능성이 있습니다.

• 불가능한 경우 판별
  1. 이동 횟수 k가 min_dist보다 작으면 불가능
  2. (k - min_dist) 가 짝수가 아니면 불가능
     • k - min_dist가 홀수면 남은 이동 횟수를 의미 없이 소모해야 하는데, 되돌아 올 수 있는 경로가 없어지므로 불가능하다.

2. 가장 빠른 사전 순으로 탐색 진행 (Greedy)

이제 (x, y)에서 (r, c)로 가는 가장 빠른 사전순 경로를 찾습니다.

• 'd' → 'l' → 'r' → 'u' 순서로 이동 시도
• 이동이 가능하면 바로 이동 (정렬 불필요)
• k = 0이 되면 종료

코드

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

using namespace std;

struct point{
    int x, y, count;
    string list;
};
int dy[4] = {0, -1, 1, 0};
int dx[4] = {1, 0, 0, -1};
char listup[4] = {'d', 'l', 'r', 'u'};

string solution(int n, int m, int x, int y, int r, int c, int k) {
    int min_dist = abs(x - r) + abs(y - c);
    
    if (min_dist > k || (k - min_dist) % 2 != 0) {
        return "impossible";
    }
    
    string answer = "";
    
    while (k > 0) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }
            
            int new_dist = abs(nx - r) + abs(ny - c);
            if (new_dist <= k - 1) {
                answer += listup[i];
                x = nx;
                y = ny;
                k--;
                break;
            }
        }
    }
    
    return answer;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!