[프로그래머스][level4] 미로 탈출 (C++)

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

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

 

 

[난이도] level4
[유형] 비트마스크

[풀이]
트랩에는 연결된 간선이 역방향인 경우와 정방향인 경우 두가지 상태가 있습니다.
간선이 역방향이려면 트랩에 홀수번 방문한 상태여야 하며, 정방향인 경우는 방문을 안했거나
짝수번 방문한 상태입니다.

트랩의 개수가 최대 10개밖에 되지 않으므로 10개의 비트로 아래와 같이 트랩의 상태를 저장할 수 있습니다.
0000000000(0)~1111111111(2^10-1) (0인 경우 정방향, 1인 경우 역방향)

이를 이용해 vector<pair<int,int>> adj[1025][1001] 형태의 adj[state][node] 2차원 인접리스트를 선언한 뒤
state에 따라 올바른 간선 방향을 가지는 인접 리스트를 각각 만들어줍니다.

트랩의 개수가 k개라면 인접 리스트는 총 2^k개가 나올 수 있습니다.
만약 어떤 노드 u,v를 연결하는 간선이 입력으로 주어질 때,
i)   u,v가 모두 정방향인 경우(둘다 트랩이 아니거나, 트랩이어도 state 비트마스크에서 두 트랩 모두 0)
      u,v는 u->v 방향 그대로 저장

ii)  u,v 둘중 하나가 트랩이면서 역방향인 경우
      간선을 뒤집어야 하므로 v->u 방향으로 저장

iii) u,v 모두 트랩이면서 역방향인 경우
      이 경우에는 간선이 u에 의해 한번 뒤집히고, v에 의해 또한번 뒤집히므로 결국 정방향인 상태가 됩니다.
      그대로 u->v 방향으로 저장

위와 같이 state에 따라서 간선이 역방향, 정방향인지 정할 수 있고
각 state마다 인접 리스트(그래프)가 생성되게 됩니다.

이를 이용해 int dist[1025][1001] 배열을 선언하여
dist[state][node] : 현재 트랩의 상태가 state 일때, node까지의 최단 거리를 업데이트 해주는 BFS를
이용하여 end node까지의 거리를 구할 수 있습니다.
시간 제한이 10초로 넉넉하여 다익스트라를 사용하지 않고 일반 BFS를 사용하여도 AC를 받았습니다.

현재 노드가 cur 일때, 연결된 다음 노드 nxt가 트랩이라면 nxt에 연결된 간선이 뒤집어져야 하므로
state 비트를 변경해주어야 합니다. 간단히 bit xor 연산으로 다음 state를 구할 수 있습니다.
현재 state가 bit이고 nxt가 i번째 trap 이라면 next_bit = bit ^ (1<<i) 이 됩니다. i번째 bit만 뒤집어주면 되기 때문입니다.

다익스트라로 구현하면 end 노드에 처음 도착한 순간이 최단거리 이지만
BFS로 구현하였기 때문에 항상 최적의 경로로 방문하는 것이 아니어서
더이상 방문할 노드가 없을 때까지 계속 방문하며 최솟값을 업데이트 해주어야 합니다.

 

#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
int dist[1025][1001];
bool trap[1001];
map<int,int> trapidx;
vector<pair<int,int>> adj[1025][1001];
bool isFlip(int a,vector<int>& flag){
    return trap[a] && flag[trapidx[a]];
}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    for(int i=0;i<traps.size();i++) {
        trap[traps[i]]=1;
        trapidx[traps[i]]=i;
    }
    for(int i=0;i<(1<<traps.size());i++){
        vector<int> flag(traps.size(),0);
        for(int j=1;j<=n;j++) dist[i][j]=9e8;
        for(int j=0;j<traps.size();j++) {
            if(i&(1<<j)) flag[j]=1;
        }
        for(auto& r : roads){
            int u=r[0],v=r[1],c=r[2];
            int cnt = isFlip(u,flag)+isFlip(v,flag);
            if(cnt==1) adj[i][v].push_back({u,c});
            else adj[i][u].push_back({v,c});
        }
    }
    queue<pair<int,int>> q;
    dist[0][start]=0;
    q.push({0,start});

    int ans=9e8;
    while(!q.empty()){
        auto [bit,cur] = q.front(); q.pop();
        if(cur==end) ans=min(ans,dist[bit][cur]);
        for(auto [nxt,d] : adj[bit][cur]){
            int nb = bit;
            if(trap[nxt]) {
                int i = trapidx[nxt];
                nb ^= (1<<i);
            }
            if(dist[nb][nxt] > dist[bit][cur]+d){
                dist[nb][nxt]=dist[bit][cur]+d;
                q.push({nb,nxt});
            }
        }
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/미로_탈출.cpp