문제

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

문제 링크

풀이

문제를 보자마자 DFS로 풀면 될 것 같았다. 하지만 무턱대고 완전탐색을 해버리면 당연히 시간초과가 나올 것이다.
그래서 몇가지 최적화를 해줘서 불필요한 경로를 계산하지 않도록 DFS코드를 작성해야 했다.


1. DFS를 돌기 전 미리 "impossible"인 경우를 계산한다.

• 처음 위치에서 탈출까지 최단 거리(remain)를 미리 계산하고 그 값이 탈출까지 이동해야 하는 거리(k)보다 큰 경우
• remain과 k의 차이가 홀수인 경우
  • k칸 이동 후 정확히 (r,c)에 위치할 수 없다. 아무리 가까워도 바로 옆칸만 가능하다.

int remain = abs(x-r) + abs(y-c);
    if ((k - remain) % 2 != 0 || remain > k) {
        answer = "impossible";
    }

2. 문자열 사전 순으로 움직였기 때문에 남은 이동 횟수가 0 인데 위치가 r,c 인 경우가 처음 나오는 경우가 우리가 원하는 해이다. 해를 찾았다면 다른 dfs를 멈춘다.

void dfs( ... ){
    if (dfsExit){
        return;
    }
    
    // ... 
    
    if (depth == k){
        if (x == r && y == c){
            // cout << stack << endl;
            answer = stack;
            dfsExit = true;
        }
        return;
    }
}

3. 현 위치에서 목적지까지 최단 거리가 남은 움직임 수 보다 먼 경우를 제거

• DFS를 돌면서 한 칸씩 움직일 때마다 현재위치에서 목적지까지의 거리가 남은 거리보다 긴 경우에 DFS를 재귀호출하지 않고 리턴한다.

if (k - depth < abs(x-r) + abs(y-c)){
        return;
    }
// depth는 dfs에서 움직인거리를 의미한다.

하지만 재귀호출을 통한 DFS가 아니더라도 문제를 풀 수 있다.

문제에서는 사전순으로 빠른 탈출 경로를 원하므로 다음칸을 결정할 때마다 d l r u 순서로 이동이 가능한지 검사한다.
가장 먼저 이동이 가능한 경로가 탐색된 알파벳 경로가 문제에서 원하는 답이 된다.

• 이동했을 때의 위치에서 목적지까지 최단 경로가 남은 이동 횟수보다 작다면 이동 불가능한 경로이다.

검사 후 이동을 k번 반복하면 된다.

코드

DFS 풀이

#include <string>
#include <vector>

using namespace std;

struct Delta {
    string command = "dlru";
    vector<int> dx {1, 0, 0, -1};
    vector<int> dy {0, -1, 1, 0};
};

bool OOB (int x, int y, int n, int m){
    if ( 0 < x && x <= n && 0 < y && y <= m){
        return true;
    }
    else {
        return false;
    }
}

void dfs(int x, int y, vector<int>& info, const Delta& delta, string& answer, string& stack, int depth, bool& dfsExit){
    if (dfsExit){
        return;
    }
    int n = info[0];
    int m = info[1];
    int r = info[2];
    int c = info[3];
    int k = info[4];

    if (k - depth < abs(x-r) + abs(y-c)){
        return;
    }

    // printf("x: %d, y: %d, depth: %d\n", x, y, depth);
    if (depth == k){
        if (x == r && y == c){
            // cout << stack << endl;
            answer = stack;
            dfsExit = true;
        }
        return;
    }
    
    for (int d=0; d < 4; d++){
        int nextX = x + delta.dx[d];
        int nextY = y + delta.dy[d];
        if (OOB(nextX, nextY, n, m)){
            stack += delta.command[d];
            dfs(nextX, nextY, info, delta, answer, stack, depth+1, dfsExit);
            stack = stack.erase(stack.size()-1);
        }
    }
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    string stack = "";
    vector<int> info {n, m, r, c, k};
    Delta delta;
    bool dfsExit = false;
    int remain = abs(x-r) + abs(y-c);
    if ((k - remain) % 2 != 0 || remain > k) {
        answer = "impossible";
    }
    else {
        dfs(x, y, info, delta, answer, stack, 0, dfsExit);
    }
    return answer;
}

Greedy 풀이

#include <string>
#include <vector>

using namespace std;

bool OOB (int x, int y, int n, int m){
    if ( 0 < x && x <= n && 0 < y && y <= m){
        return false;
    }
    else {
        return true;
    }
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";

    string command = "dlru";
    vector<int> dx {1, 0, 0, -1};
    vector<int> dy {0, -1, 1, 0};

    bool flag = false;

    int dist = abs(x-r) + abs(y-c);
    if ((k - dist) % 2 != 0 || dist > k) {
        return "impossible";
    }
    
    while (k--){
        for (int d=0; d < 4; d++){
            printf("i: %d, k: %d \n", d, k);
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if (OOB(nx, ny, n, m)) continue;
            
            int remain = abs(nx - r) + abs(ny - c);
            if (remain > k) continue;

            x = nx;
            y = ny;
            answer += command[d];
            break;
        }


    }
    return answer;
}