프로그래머스 미로 탈출 혼내주기

 

 

 

2021 카카오톡 채용연계형 인턴쉽 코딩테스트 4번 문제.
비트마스크 + 다잌스트라로 풀면 된다. 함정 상태에 따라서 어떤 경우를 pq에 넣을지 조금 헷갈렸는데, 정방향인 경우 0번이나 2번 함정이 발동된 경우, 역방향인 경우 1번만 함정이 발동된 경우에만 다잌스트라를 이어가면 된다.

분기 때문에 생각보다 다시 풀어도 헷갈렸다... 그래도 뭔가 맺힌 한을 푼 기분!
5번은 아직도 어려워서 더 강해지면 풀어야겠다.

 

 

 

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct state {
    int from, dist, bit;
    state(int ff, int dd, int b) {
        from = ff, dist = dd, bit = b;
    }
    bool operator<(const state& s) const {
        return dist > s.dist;
    }
};

struct link {
    int to, dist; bool isTrap; 
    link(int tt, int dd, int ii) {
        to = tt, dist = dd, isTrap = ii;
    }
};

vector<link> adj[1005];
vector<link> rev[1005];

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    vector<int> trapIndex(n+1, 0);
    for(int i = 0; i < traps.size(); ++i) {
        trapIndex[traps[i]] = i+1;
    }

    for(vector<int> road : roads) {
        adj[road[0]].push_back(link(road[1], road[2], trapIndex[road[1]]));
        rev[road[1]].push_back(link(road[0], road[2], trapIndex[road[0]]));
    }

    priority_queue<state> pq;
    vector<vector<int> > dist(n+1, vector<int>((1<<(traps.size()+1)), 2e9));
    dist[start][0] = 0;
    pq.push(state(start, 0, 0));
    cout << dist[3][6] << endl;
    while(!pq.empty()) {
        auto [from, d, bit] = pq.top(); pq.pop();
        if(dist[from][bit] < d) continue;
        if(from == end) return d;
        
        for(auto [to, toDist, toTrap] : adj[from]) {
            bool valid = true;
            if(trapIndex[from] && (bit & (1 << trapIndex[from]))) valid = !valid;
            if(trapIndex[to] && (bit & (1 << trapIndex[to]))) valid = !valid;
            if(!valid) continue;
            
            int nDist = d + toDist;
            int nBit = (bit ^ (toTrap << trapIndex[to]));
            if(dist[to][nBit] <= nDist) continue;
            dist[to][nBit] = nDist;
            pq.push(state(to, nDist, nBit));
        }

        for(auto [to, toDist, toTrap] : rev[from]) {
            bool valid = false;
            if(trapIndex[from] && (bit & (1 << trapIndex[from]))) valid = !valid;
            if(trapIndex[to] && (bit & (1 << trapIndex[to]))) valid = !valid;
            if(!valid) continue;
            
            int nDist = d + toDist;
            int nBit = (bit ^ (toTrap << trapIndex[to]));
            if(dist[to][nBit] <= nDist) continue;
            dist[to][nBit] = nDist;
            pq.push(state(to, nDist, nBit));
        }
    }

    return 0;
}

int main() {
    vector<vector<int> > roads = {
        {1, 2, 1},
        {3, 2, 1},
        {2, 4, 1}
    };

    vector<int> traps = {
        2, 3
    };
    cout << solution(4, 1, 4, roads, traps);
}