2021 KAKAO 채용연계형 인턴쉽 미로 탈출

https://programmers.co.kr/learn/courses/30/lessons/81304#

코딩테스트 연습 - 미로 탈출

 

방문한 Trap을 bit로 관리한다는 생각을 떠올리니, 방탈출 문제가 생각났다. 그 문제풀이를 이 문제에 적용시켜보면 될 것 같았다.
대신 map 크기가 작아 완전탐색으로 풀었던 방탈출 문제 대신, 이 문제는 Vertex<=1000, Edge<=3000 여서 다익스트라를 적용해서 풀면 될 것 같았다.

Graph를 구성할 땐 정방향/역방향 간선을 모두 생성하고,
다익스트라 과정에서 현재 방문한 Trap의 상태를 토대로 간선을 사용할 수 있는지 확인하여 탐색을 진행한다면 쉽게 풀 수 있었다.

예를 들어 문제의 예시 1에서 Node 2(1번 Trap)의 방문 여부를 확인하여 이를 방문했을 시에는 2->1, 2->3 역뱡향 간선을 사용할 수 있게 설정하면된다.

나는 정방향 간선엔 0, 역방향 간선엔 1을 붙여 간선 방향을 구분했다.

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

using namespace std;

vector<vector<pair<pair<int, int>, int>>> map;
int cost[1001][2000];
int istrap[1001];

inline int get_bit(int target, int idx)   {return (target >> (idx-1)) & 1;}
inline int toggle_bit(int target, int idx){return target ^ (1 << (idx-1));}
inline void my_swap(int& a, int& b){int t = a; a = b; b = t;}

int get_path_type(int a, int b, int visited){
    if(istrap[b]) my_swap(a,b);
    int trap_id_a = istrap[a];
    int trap_id_b = istrap[b];
    
    if(!trap_id_a && !trap_id_b) return 0; //둘다 함정이 아니면, 두 정점을 연결하는 역방향 간선이 없다.
    else if(trap_id_a && trap_id_b){
        int bit_a = get_bit(visited, trap_id_a);
        int bit_b = get_bit(visited, trap_id_b);
        if((bit_a + bit_b) & 1) return 1; //한쪽만 방문한 적이 있으면
        else return 0;
    }
    else{
        int bit_a = get_bit(visited, trap_id_a);
        if(bit_a) return 1;
        else return 0;
    }
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = -1;
    map.resize(n+1);
    for(int i=0;i<traps.size();i++) istrap[traps[i]] = i+1;
    for(auto road : roads){
        map[road[0]].push_back({{road[1], road[2]}, 0});
        map[road[1]].push_back({{road[0], road[2]}, 1}); //역방향
    }
    for(int i=1;i<=n;i++) for(int j=0;j<1024; j++) cost[i][j] = 0xfffffff;
    
    priority_queue<pair<pair<int, int>, int>> pq;
    cost[start][0] = 0;
    pq.push({{0,start},0});
    
    while(pq.size()){
        
        int nown = pq.top().first.second;
        int nowc = -pq.top().first.first;
        int visited_trap  = pq.top().second;
        if(nown == end){
            answer = nowc;
            break;
        }
        pq.pop();
        
        for(auto next : map[nown]){
            int nextn = next.first.first;
            int nextc = next.first.second;
            int nextp = next.second;
            int next_visited_trap = visited_trap;
            int path_type = get_path_type(nown, nextn, visited_trap);
            
            if(nextp != path_type) continue;
            if(istrap[nextn]) next_visited_trap = toggle_bit(visited_trap, istrap[nextn]);
            int tcost = cost[nown][visited_trap] + nextc;
            if(tcost < cost[nextn][next_visited_trap]){
                pq.push({{-tcost,nextn}, next_visited_trap});
                cost[nextn][next_visited_trap] = tcost;
            }
        }
    }
    
    return answer;
}