2021 KAKAO INTERNSHIP [미로 탈출] [C++]

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

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

---

문제 요약

그래프 공간 속에서 일부 정점 중 함정이 있다 

함정의 역할은 밟는 순간 해당 정점과 연결된 모든 간선을 뒤집힌다

모든 간선은 cost 가 다르다

시작 정점이 주어지고 도착 정점이 주어질 경우 최소비용을 계산하라

 

---

나의 풀이

이 문제는 꽤 오래 생각해야 풀 수 있었다.

이 문제는 언듯 보면 최단경로를 계산하는 여느 문제들과 다를 점이 없지만

• 함정 때문에 간선이 이동하면서 실시간으로 지도가 바뀐다.
• 갔던 곳을 다시 방문해도 된다(사실 다시 방문해야만 갈 수 있는 경로도 있을 것이다)

갔던 곳을 다시 방문해야 되기 때문에 다익스트라처럼은 풀 수 없다고 생각했고

 

다이내믹 프로그래밍으로 푸는 문제인지 그리디적인 해법이 있는 문제인지 계속 고민했다

쉽게 단방향으로 생각하기에는 예외가 너무 많았고 그리디적인 해법이 있다고 하기엔 뒤집히는 간선이 너무 나의 머리를 아프게 했다.

계속 고민하다가 결국에는 특정결과가 다음 결과에 영향을 미치긴 하지만 전부 시도해보아야 하는 문제인 것을 깨달았다

 

함정이 10 개인 걸보고 10개의 함정으로 나타낼 수 있는 케이스는 2^10 개 즉 1024개이고 

정점의 개수는 1000개 이기 때문에 

모든 정점별로 함정이 존재할 수 있는 모든 케이스의 최소비용을 저장하는 방식으로 저장을 해야 한다고 생각했다.

 

배열 \(d [i][j]\)  \( i <=1000 , j <=1024 \)을 준비

i는 정점의 번호 j는 현재 함정의 on off 정보를 담고 있는 비트 마스크로 정의를 한 후 매번 최소비용만 queue에 갱신되도록 BFS를 돌려주었다.

 

주어진 조건에 딱 들어맞는 비트 마스킹을 이용한 완전 탐색 문제였기에 다른 문제에 비해 생각하는 시간이 많이 걸렸었던 것 같다

 

만약 문제가 모든 케이스를 봐야 될 거 같고 정보의 양이 많다면 어떻게 압축시킬지 비트 마스킹을 이용한 자료구조를 생각해보는 게 좋을 것 같다.

---

소스코드

#include<bits/stdc++>
#define INF 0x3f3f3f3f
using namespace std;
int dist[1001][1025];
struct edge{
    int to;
    int cost;
    bool normal;   
    edge(int t,int c , bool b): to(t),cost(c),normal(b){}
};
vector<edge> vertex[1001];
map<int,int> tr;
bool isTrap(int &idx){
    if(tr.find(idx)!=tr.end())return true;
    return false;
}
bool isReverse(int &bitmask , int &vertex){
    return isTrap(vertex) && (bitmask & (1<<tr[vertex]));
}
bool isPossible(int from, edge e , int bitmask){
    int to = e.to;

    if(!isTrap(from)&&!isTrap(to)){
        return e.normal;
    }

    if(isReverse(bitmask , from)^isReverse(bitmask , to)){
        return !e.normal;
    }else{
        return e.normal;
    }

}
int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = INF;
    for(int i=0;i<1001;i++){
        for(int j=0;j<1025;j++){
            dist[i][j] = INF;
        }
    }

    int tr_size = traps.size();
    for(int i=0;i<traps.size();i++){
        tr.insert({traps[i],i});
    }

    for(auto road : roads){
        int from=road[0];
        int to=road[1];
        int cost=road[2];
        vertex[from].emplace_back(to,cost,true);
        vertex[to].emplace_back(from,cost,false);
    }

    dist[start][0]=0;  
    queue<pair<int,int>> q;
    q.push({start,0});

    while(!q.empty()){
        int cur = q.front().first;
        int bitmask = q.front().second;
        int cost = dist[cur][bitmask];
        q.pop();
        for(int i=0;i<vertex[cur].size();i++){
            if(isPossible(cur,vertex[cur][i],bitmask)){

                int next = vertex[cur][i].to;
                int next_cost = cost+vertex[cur][i].cost;
                int nextBitmask = bitmask;
            
                if(isTrap(next)){
                    nextBitmask = nextBitmask ^ (1<<tr[next]);
                }

                if(dist[next][nextBitmask]>next_cost){
                    dist[next][nextBitmask] = next_cost;
                    q.push({next,nextBitmask});
                }
                

            }
        }
        
    }
    for(int i=0;i<(1<<tr_size);i++){
        answer = min(answer , dist[end][i]);
    }
    return answer;
}