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

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

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

1. 주의할 점

- 10가지 Trap의 상태를 어떤 방식으로 저장할 것인가

- 최단경로 알고리즘인 다익스트라 알고리즘에 대해 알고 있어야 한다

 

2. 구현 (아래 색칠된 3개가 가장 중요한 비트마스크 수식)

- Trap의 상태가 최대 10개다 + 다익스트라를 사용해야 할 것 같다 → Trap의 상태가 공용으로 설정되면 안된다 → 비트마스킹을 사용한다

- 현재 Node, 총 이동거리, 현재 Trap의 상태를 나타내는 Info 객체를 사용한다

- Map을 통해 Trap인 Node가 몇 번째 Trap으로 설정할 것인지 저장한다(0~9번째 Trap)

- V[][] 벡터를 통해 간선들의 정보를 저장하며, [][0]일때는 정방향, [][1]일때는 역방향을 저장한다. 단, 출발이나 도착 Node가 스위치인 경우에만 [][1]에 추가한다

- Dist[n][trap] 배열을 통해 n번 Node까지 trap의 trap상태를 가지고 도착했을 떄의 최단거리를 저장한다

- 아래의 코드를 통해 현재 노드인 cidx와 다음 노드인 next Node의 Trap이 활성화(= 1)인지 비활성화(=0)인지 판별한다

//cidx Node의 Trap상태 검사
if(m.find(cidx)!=m.end() && (cc & (1<<m[cidx]))>0)
            cidxPushed = 1;

//next Node의 Trap상태 검사
if(m.find(next)!=m.end() && (cc & (1<<m[next]))>0)
            nextPushed = 1;

- 아래의 코드를 통해 현재 Node와 도착 Node를 비교하여 둘 다 스위치가 켜져있거나 꺼져있으면 [][0] 간선을 , 1개만 켜져있는 경우에는 [][1] 간선을 바라봐야한다. 따라서, 간선의 방향을 나타내는 K와 flag가 일치하지 않다면 Continue를 수행

int flag = cidxPushed ^ nextPushed;
		if(k!=flag) continue;

- 다음으로 넘어가려는 Node가 Trap인 경우, 상태를 변화시키기 위해 다음과 같은 코드를 우선순위큐에 삽입한다

if(m.find(next)!=m.end())   pq.push({next,cv+nv,cc ^ (1<<m[next])});

 

#define MAX 987654321
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
struct info{
    int idx,val,cur;        //현재 Node, 총 이동거리, 현재 Trap들의 상태
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};

map<int,int> m;     //<i,j>: i번쨰 trap은 j번째 Node다
vector<info> v[1001][2];        //[][0]: 정방향, [][1]:역방향
int dist[1001][1024];       //[n][v]: v상태의 trap이 눌렸을 때, n에 도달하는 최소 값
int tnum;
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = 0;
    tnum = traps.size();
    for(int i=0;i<tnum;i++)
        m[traps[i]]=i;
    for(int i=0;i<roads.size();i++){
        int from = roads[i][0];
        int to = roads[i][1];
        int val = roads[i][2];
        v[from][0].push_back({to,val,0});
        if(m.find(from)!=m.end() || m.find(to)!=m.end())
            v[to][1].push_back({from,val,0});
    }
    
    for(int i=1;i<=n;i++)
        for(int j=0;j<(1<<tnum);j++)
            dist[i][j]=MAX;
    
    priority_queue<info,vector<info>,cmp> pq;
    pq.push({start,0,0});
    dist[start][0]=0;
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int cv = pq.top().val;
        int cc = pq.top().cur;
        pq.pop();
        if(cidx==end){
            answer = cv;
            break;
        }
        int cidxPushed = 0;
        if(m.find(cidx)!=m.end() && (cc & (1<<m[cidx]))>0)
            cidxPushed = 1;
        for(int k=0;k<2;k++){
            for(int i=0;i<v[cidx][k].size();i++){
                int next = v[cidx][k][i].idx;
                int nv = v[cidx][k][i].val;
                int nextPushed = 0;
                if(m.find(next)!=m.end() && (cc & (1<<m[next]))>0)
                    nextPushed = 1;
                int flag = cidxPushed ^ nextPushed;
                if(k!=flag) continue;
                if(dist[next][cc]>cv+nv){
                    dist[next][cc]=cv+nv;
                    if(m.find(next)!=m.end())   pq.push({next,cv+nv,cc ^ (1<<m[next])});
                    else    pq.push({next,cv+nv,cc});
                }
            }
        }
    }
    return answer;
}