프로그래머스 미로 탈출 (2021 카카오 채용연계형 인턴십)

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

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

 

문제접근법 : 어떻게 풀었냐에 따라 달라지겠지만

제가 접그했던 방법을 설명해드릴께요 대표적으로 비트마스크를 이용하게 됐는데

 

문제 그래프처럼 단방향 그래프이지만

trap 노드를 밟을때마다 그노드에 들어오는 방향이든 나가는 방향이든 반대방향이 되버립니다.

하지만 그노드를 다시밟으면 다시 원상복구가 되겠지요

그렇다면 2번테스트 케이스를 전부 그려보면

아래와같은 그림이 나옵니다.

이 그림에서 0번 STATE는 초기의 그래프이지만 어떤 TRAPS 노드도 밟지 않은상태가 되며

1번 STATE는 2번 노드를 밟은 상태이며 마찬가지로 2번 STATE는 3번 노드만 밟거나

3번 STATE는 2,3 노드를 밟은 상태입니다. 여기서 몇번을 밟든 위 그래프 4가지중 한개에밖에 나오지 않습니다.

즉 TRAPS의 길이에 따라 2^(TRAPS의 길이) 만큼 그래프가 생성되고 그STATE에 따라 모든 그래프를 만들어서 

최단거리를 구해야했습니다. 그렇기에

이문제를 해결하기위해선 비트마스크 + 다익스트라를 이용했어야 했습니다.

 

 

그렇다면 그래프는 어떻게 만들까요? 위와같이 2^(TRAPS의 길이) 만큼 그래프를 만들어야하는데

처음 TRAPS를 정렬한후 상태들에 Index를 부여합니다.

그래야 위와 테이블같은 표가 성립할수있습니다. 또한 1,2번 STATE를 확인하면

V1->V2로 가는 트랩 하나를 건드렸을경우 그로 가는 방향은 반대방향이지만

3번 STATE를 확인해보시면 3->2로가는 노드가 2,3번 노드 모두 트랩이기에 변경되지 않고 상태를 유지합니다.

즉 STATE에 맞게 하나만 트랩인경우 V1->V2로 가는것을 SWAP시켜 V2->V1로 만들지만 

둘다 TRAP인경우나 둘다 아닌경우는 V1->V2 그대로 가도록 만듭니다.

 

이것을 비트연산을하게되면 XOR을 하면 둘다 트랩인경우와 아닌경우를 구별할수있습니다.

또 다익스트라를 돌리게되면 

현재 내가 트랩인경우 해당 비트를 껏다 켜야하는데 그에해당하는 BIT를 1로 켜서 XOR시킨다면

0이었던 상태가 1이될것이고 1이었던 상태가 0이 되기때문에 XOR을 유용하게 사용할수 있습니다.

 

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; typedef pair<int, int> p; vector<p> v[1024][1001]; vector<int> trap; struct point {     int cur, sumcost, state;     friend bool operator<(const point& a, const point& b) {         return a.sumcost > b.sumcost;     } };   int dijkstrak(int start,int end,int n,int statesize) {     vector<vector<int>> dist(1 << statesize, vector<int>(n + 1, 1e8));     priority_queue<point> pq;     dist[0][start] = 0;     pq.push({ start,0,0 });     while (!pq.empty()) {         int cur = pq.top().cur;         int sumcost = pq.top().sumcost;         int state = pq.top().state;         pq.pop();         //현재내가 트랩이라면 그비트를 키거나 꺼줘야함         if (trap[cur] != -1) {             state ^= (1 << trap[cur]);         }         for (int i = 0; i < v[state][cur].size(); i++) {             int next = v[state][cur][i].first;             int cost = v[state][cur][i].second+sumcost;             if (dist[state][next] > cost) {                 dist[state][next] = cost;                 pq.push({ next,cost,state });             }         }     }     int res = 1e8;     for (int i = 0; i < dist.size(); i++)         res = min(res, dist[i][end]);     return res; } int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {     int answer = 0;     trap = vector<int>(n + 1,-1);     sort(traps.begin(), traps.end());     for (int i = 0; i < traps.size(); i++) {         trap[traps[i]] = i;     }     //트랩을 밟아서 만들수있는 모든 경우의수     for (int state = 0; state < (1 << traps.size()); state++) {         for (auto &r : roads) {             int a = r[0];             int b = r[1];             int c = r[2];             //두노드중 하나라도 트랩인경우             if ((trap[a] != -1 || trap[b] != -1)) {                 int left = (state & (1 << trap[a])) ? 1 : 0;                 int right = (state & (1 << trap[b])) ? 1 : 0;                 //하나만 트랩일때만 swap                 if (left^right)                     swap(a, b);             }             v[state][a].push_back({ b,c });         }     }     return dijkstrak(start,end,n,traps.size()); } Colored by Color Scripter

cs

 

문제 푸는것도 고생했지만 글작성하는것도 은근히 고생했네요 ㅠ.ㅠ

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.