[ALGORITHM] LEVEL4 2021 카카오 채용연계형 인턴십 - 미로 탈출

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

프로그래머스

생각의 흐름

1. 최단거리 -> 다익스트라 사용
2. 함정 활성화, 비활성화만 구분하면 되지 않을까?(실패)
   • 만약 함정 양쪽이 활성화 되어 있는 경우 -> 함정 활성화가 되어있지만 원래 방향으로 이동하기 때문 
3. 함정 활성화 상태를 비트마스킹으로 저장하자
4. way에 정방향 간선은 true로 역방향 간선은 false로 저장을 하자
5. 일반 노드와 비활성 함정 노드는 false로 같은 취급 활성 함정 노드만 true로 취급하자
6. 둘 중 하나만 활성화 되어 있는 경우 역방향 간선으로만 움직이므로 XOR을 이용하자

해설

이 문제는 경우가 4가지가 나오게 된다. (비활성 함정 노드는 일반 노드 취급)

1. 일반 노드 -> 일반 노드

2. 일반 노드 -> 활성 함정 노드

3. 활성 함정 노드 -> 비활성 함정 노드

4. 활성 함정 노드 -> 활성 함정 노드

1 -> 2로 가는 경로의 경우

1번은 비활성 노드 = false

2번은 만약 활성화 = true

false == true -> false이므로 1->2로 가는 간선은 true일때만 이용가능하여 이동하지 못하게 된다.

 

3->2로 가는 경우

2번이 활성화 = true

3번이 활성화 = true

true == true -> true 이므로 3->2로 가는 간선은 정방향 이므로 이동 가능하게 된다.

 

2->3으로 가는 경우

2번이 활성화 = true

3번이 비활성화 = false

true == false -> false 이므로 2->3은 역방향 간선이어서 이동 가능하게 된다.

 

코드

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

using namespace std;

vector<tuple<int, int, bool> > way[1001];
int dist[1001][1<<11];
int trapper[1001];

struct dat{
  int cost, node, vst_trap;
    
    bool operator<(const struct dat& d) const{
        return cost > d.cost;
    }
};

bool cmp(vector<int>& a, vector<int>& b){
    return a[2] < b[2];
}

int dijkstra(int start,int end){
    priority_queue<dat> pq;
    
    dist[start][0]=0;
    pq.push({0,start,0});
    
    while(!pq.empty()){
        int node=pq.top().node;
        int cost=pq.top().cost;
        int vst_trap=pq.top().vst_trap;
        
        pq.pop();
        
        if(dist[node][vst_trap] < cost)
            continue;
        
        if(node == end)
            return cost;
        
        for(int i=0,sz=way[node].size();i<sz;++i){
            int next,ncost;
            int nstate = vst_trap;
            bool can_vst;
            
            tie(next,ncost,can_vst) = way[node][i];
            ncost+=cost;
            can_vst = can_vst == ((1 & nstate >> trapper[next]) == (1 & nstate >> trapper[node]));
            if(trapper[next])
                nstate = (1 & nstate >> trapper[next]) ? (nstate - (1 << trapper[next])) : (nstate | 1 << trapper[next]);
            
            
            if(dist[next][nstate] <= ncost || !can_vst)
                continue;
            
            dist[next][nstate]=ncost;
            pq.push({ncost,next,nstate});
        }
    }
    return -1;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = 0;
    
    fill(&dist[0][0],&dist[n][1<<11],987'654'321);
    sort(roads.begin(),roads.end(), cmp);
    for(int i=0,sz=traps.size();i<sz;++i){
        trapper[traps[i]]=i+1;
    }
    for(int i=0,sz=roads.size();i<sz;++i){
        int st = roads[i][0];
        int ed = roads[i][1];
        int cost = roads[i][2];
        
        way[st].push_back({ed,cost,true});
        if(trapper[st] || trapper[ed])
            way[ed].push_back({st,cost,false});
    }
    
    answer=dijkstra(start,end);
    
    return answer;
}