[프로그래머스 LV.4] 미로 탈출 (C++) - 2021 카카오 채용연계형 인턴십

1. 문제

LV 4.미로 탈출 - 2021 카카오 채용연계형 인턴십

2. 문제 풀이

우선, 출발 방과 도착 방의 정보가 주어지고, 노드수 제한 $n <= 1000$ 이므로 다익스트라 알고리즘을 떠올릴 수 있습니다.

그런데 일반적인 다익스트라 문제와 다른 점은, 모든 trap들의 발동 상태를 알지 못하면 현재 내가 어떤 노드 x에 서있을 때 어떤 노드로 갈 수 있는지 모른다는 것입니다.

여기서 함정방의 개수가 최대 10개임을 이용하여, 비트마스킹을 사용할 수 있습니다.

일반적인 경우에 graph[x] 에 x에서 갈 수 있는 모든 간선들이 담겨있지만,

비트마스킹을 사용하여 graph[x][bit] 에 모든 trap들의 발동 상태가 bit일 때, x에서 갈 수 있는 모든 간선들을 담으면 됩니다.

이때 노드 수와 간선 수는 각각 $2^{traps}$를 곱한 만큼의 개수를 갖게 됩니다.

따라서 시간복잡도는 $O(roads * 2^{traps} * log_2(n * 2^{traps})) => O(roads * 2^{traps} * log(n))$ 가 되고,

$roads <= 3000, 2^{traps} <= 1024, n <= 1000$ 이므로

약 6133만 번의 연산이 발생하지만 시간 안에 동작합니다.

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
 
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int mask=1<<traps.size();
    vector<int> temp(mask,1e9);
 
    //시작 방에서 i번 방으로 이동하는 최단거리. j는 trap의 bitmask 상태를 나타낸다.
    vector<vector<int>> dist(n+1,temp);
 
    vector<vector<tp>> temp2(mask);
    vector<vector<vector<tp>>> graph(n+1,temp2);
 
    //b[i]==-1 : i번 방은 함정 방이 아니다. / b[i]>=0 : i번 방은 b[i]번째 함정 방이다.
    vector<int> b(n+1,-1);
    for(int i=0;i<traps.size();i++)b[traps[i]]=i;
 
    //모든 trap발동 상태에 대해, 간선 방향을 미리 구해둔 그래프를 만든다.
    for(int bit=0;bit<mask;bit++)
        for(auto edge:roads){
            int x=edge[0],y=edge[1],cost=edge[2];
            //현재 간선의 양끝 방중 하나의 trap만 발동중일 경우, 간선방향을 swap한다.
            if((b[x]>=0&&(bit>>b[x]&1))^(b[y]>=0&&(bit>>b[y]&1)))swap(x,y);
            //방 x에서, trap발동 상태가 bit일 때, {도착지, 도착했을 때 trap발동 상태, 도착하는 비용}이 담겨있는 간선을 추가한다.
            graph[x][bit].push_back({y,b[y]<0?bit:bit^(1<<b[y]),cost});
        }
 
    priority_queue<tp,vector<tp>,greater<tp>> pq;
    //아무 트랩도 발동하지 않은 상태에서 start 방에서 다익스트라 시작.
    pq.push({0,start,0}),dist[start][0]=0;
    while(!pq.empty()){
        auto [cost,node,bit]=pq.top();pq.pop();
        if(cost>dist[node][bit])continue;
        for(auto [nxNode,nxBit,w]:graph[node][bit]){
            if(dist[nxNode][nxBit]>cost+w){
                dist[nxNode][nxBit]=cost+w;
                pq.push({dist[nxNode][nxBit],nxNode,nxBit});
            }
        }
    }
    return *min_element(dist[end].begin(),dist[end].end());
}

4. 코드 설명

for(int bit=0;bit<mask;bit++)

이 for문을 통해 모든 trap들의 발동 상태를 탐색하게 됩니다.

trap의 개수 = 4 인 경우를 예로 들어보면,

ex 1) bit = 3일 때 : 이진법으로 나타내면 0011(2) 이므로, 0,1번 trap이 발동 중이고, 2,3번 trap은 발동 중이지 않은 상태입니다.

ex 2) bit = 9일 때 : 이진법으로 나타내면 1001(2) 이므로, 0,3번 trap이 발동중이고, 1,2번 trap은 발동 중이지 않은 상태입니다.

ex 3) bit = 0일 때 : 이진법으로 나타내면 0000(2) 이므로, 어떤 trap도 발동중이지 않은 상태 (= 시작상태)입니다.

 

if((b[x]>=0&&(bit>>b[x]&1))^(b[y]>=0&&(bit>>b[y]&1)))swap(x,y);

간선이 뒤집히는 경우입니다.

여기서 b[x]>=0 은 'x번 방이 함정방인가?'를 의미하고, bit>>b[x]&1 는 'b[x]번째 trap(= x번 방의 trap)이 발동 중인가?'를 의미하는 bool값입니다. ('n번 방'과 'n번째 방'의 의미를 헷갈리지 않게 주의해 주세요. 저도 헷갈리네요;;)

'>>' 연산은 비트를 오른쪽으로 shift 한다는 뜻인데, 익숙하게 말하자면 bit를 2로 b[x]번 나눈다는 뜻과 같습니다.

ex 1) bit=13, x=5, b[x]=2인 경우 :

bit>>b[x] & 1 => 13>>2 & 1 => 1101(2)>>2 & 1=> 110(2)>>1 & 1 => 11(2) & 1 => 11(2) & 01(2) => 1(2)

∴ 결괏값이 1(true)이므로, 5번 방은 현재 trap이 발동 중이라는 의미입니다.

ex 2) bit=5, x=3, b[x]=1인 경우 :

bit>>b[x] & 1 => 5>>1 & 1 => 101(2)>>1 & 1=> 10(2) & 1 => 10(2) & 01(2) => 0(2)

∴ 결괏값이 0(false)이므로, 3번 방은 현재 trap이 발동 중이지 않다는 의미입니다.

만약 어떤 간선의 양쪽 방의 trap이 모두 발동 중이라면, 그 간선은 뒤집으면 안 되므로 XOR 연산(^)을 사용합니다.

 

graph[x][bit].push_back({y,b[y]<0?bit:bit^(1<<b[y]),cost});

이제 새로운 간선을 추가할 때, 도착지 y로 갔을 때 그 방이 함정 방이라면 bit 상태를 갱신해주어야 합니다.

만약 b[y]<0 (= 방 y가 함정방이 아님)이라면, bit 상태는 그대로이고,

b[y]>=0 (= 방 y가 b[y]번째 함정방임)이라면, bit^(1<<b[y]) 와 같이 상태를 바꿔주면 됩니다.

ex 1) bit=12, b[y]=2 인 경우 :

1100(2) ^ 0100(2) = 1000(2) -> 켜져 있던 2번째 함정방을 끈 것입니다. (0번째 방부터 시작함에 유의해주세요.)

ex 2) bit=1, b[y]=3 인 경우 :

0001(2) ^ 1000(2) = 1001(2) -> 꺼져있던 3번째 함정방을 켠 것입니다.

이후 하던 대로 다익스트라를 돌려주시면 되고, 시작 bit=0 (모든 trap이 꺼져있는 상태)에서 시작하시면 됩니다.

 

return *min_element(dist[end].begin(),dist[end].end());

마지막으로 end 방에 도착한 모든 bit 상태에 해당하는 거리 중 최솟값을 return 하면 됩니다.