미로 탈출 명령어

예전부터 계속 풀어보려고 했는데 못 풀었던 문제를 드디어 풀어봤다. 작년에 테스트에서 봤을 때 대체 어떻게 푸는건지 정말 감이 안왔었는데 비로 효율적인 풀이는 절대 아니겠지만 그래도 많이 생각해보고 노력한 끝에 풀게 되었다.

(문제 설명 생략) 이 문제의 특이한 점은 일반적인 탐색 문제랑 다르게 방문했던 위치를 다시 방문할 수 있는 점인데 'E' 지점까지 같은 경로를 간다해도 사전순으로 가장 짧은 경로를 구해야한다.

난 이 문제에 다익스트라 방식을 적용 시켜서 PQ가 항상 사전 순으로 빠른 경로만을 선택할 수 있게 했다. 그런데 이 방식으로 하면은 시간초과가 나서 4차원 visited 배열로 꾸역꾸역 했는데도 마지막 테케가 통과가 안됐다. 왜지??

했는데 IMPOSSIBLE 조건을 내가 고려를 안했다. IMPOSSIBLE 조건은 정말 무슨 짓을 해도 'E' 까지의 경로를 찾을 수 없을 때다.

이때 계산된 방법은, 시작점과 끝점의 좌표를 이미 알고 있기 때문에 두 점의 차이를 알아낸다. 그 후에 내가 이동할 수 있는 K무브와 차이가 홀수 일경우, 절대 그 경로에 닿지 못하고, 혹은 K무브보다 멀 경우 절대 닿지 못한다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

struct Node{
    int x, y, currDist; 
    string currPath; 
};

struct NodeCompare{
    bool operator()(Node& a, Node& b){
        return a.currPath > b.currPath; 
    }
};

struct Dir{
    char direction; 
    int x, y; 
};

bool visited[51][51][4][2501]; 

vector<Dir> dir = {{'d',1,0}, {'l',0,-1}, {'r',0,1},{'u',-1,0}}; 
map<char,int> dirMap = {{'d',0}, {'l',1}, {'r',2}, {'u',3}}; 

string solution(int n, int m, int x, int y, int r, int c, int k) {
    int remain = abs(x-r) + abs(y-c);
    if ((k - remain) % 2 != 0 || remain > k) {
        return "impossible";
    }
    string answer = "";
    priority_queue<Node, vector<Node>, NodeCompare> pq; 
    pq.push({x-1,y-1,0,""}); 
    memset(visited,false,sizeof(visited)); 
    
    while(!pq.empty()){
        
        Node node = pq.top(); 
        pq.pop(); 
        
        int currX = node.x, currY = node.y, currDist = node.currDist; 
        string currPath = node.currPath; 
        
        //cout << currPath << ' ' << currX << ' ' << currY << ' ' << currDist << endl; 
        
        if(currDist == k && currX == r-1 && currY == c-1){
            return currPath; 
        }
        
        for(Dir& d : dir){
            int nX = currX + d.x; 
            int nY = currY + d.y; 
            string newPath = currPath + d.direction; 
            
            if(nX < 0 || nY < 0 || nX >= n || nY >= m || currDist > k) continue; 
            
            if(!visited[nX][nY][dirMap[d.direction]][currDist]){
                visited[nX][nY][dirMap[d.direction]][currDist] = true; 
                pq.push({nX, nY,currDist+1,newPath}); 
            }
        }
    
    }
    return "impossible";
}

그리디 방법으로는 아래와 같다.

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> dir = {{1,0},{0,-1},{0,1},{-1,0}}; 
vector<char> letter_dir = {'d','l','r','u'}; 

string answer = "";
string ret = "impossible";
bool found = false; 

int N, M; 


int get_dist(int x, int y, int a, int b){
    return abs(x - a) + abs(y - b); 
}

void dfs(int cnt, int currX, int currY, int k, int r, int c){
    if(found) return; 

    int dist = get_dist(currX, currY, r, c); 
    if(k - cnt < dist) return; //내가 현재 이동할 수 있는 거리로 목적지에 도착할 수 없을때 
    if(cnt == k){
        if(currX == r && currY == c){
            found = true; 
            ret = answer; 
        }
        return; 
    }
    for(int i = 0; i < 4; i++){
        int nX = currX + dir[i].first; 
        int nY = currY + dir[i].second; 
        if(nX <= 0 || nY <= 0 || nX > N || nY > M) continue; 
        answer += letter_dir[i]; 
        dfs(cnt + 1, nX, nY,k, r, c); 
        answer.pop_back(); 
    }
}

string solution(int n, int m, int x, int y, int r, int c, int k) {
    N = n, M = m; 
    if((k - get_dist(x,y,r,c)) % 2 == 1) return "impossible"; 
    dfs(0,x,y,k,r,c); 
    return ret;
}

결론적으로 탐색을 하면서 내가 과연 목적지에 도착할 수 있나를 계속 생각해야 했다. 아깝다..