[카카오 2021 채용연계형 인턴십] 미로탈출 (c++)

 

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

위 문제에 대한 해설입니다.

 

우선 문제를 풀기 전 내가 가장 고생했던 부분은 trap 노드의 개수가 10개가 최대라는 점이다.

처음에 trap 노드 개수의 제한이 없고, 즉 input n의 개수인 3000개까지 trap이 생길 수 있다고 생각하고 고생을 좀했다.

 

만약 trap의 개수가 10개라는 정보를 안다면, "trap 노드" 라고하는 매우 복잡한 노드를 따로 처리하는 방식을 어렵지 않게 생각할 수 있을 것이다.  

 

하지만 그럼에도 이 문제가 어려웠던 점은, 기존에 우리가 알던 "최단 거리" 알고리즘의 전제를 바꾸어 놓는다는 것 이다.

이 문제의 경우, 특정 시작점에서 도착점으로 향하는 최단거리를  찾는 "다익스트라" 알고리즘을 써야한다.

하지만 다익스트라의 경우 어떠한 노드에 대한 최단거리를 찾고나면 끝이고, 해당 노드를 다른 방식으로 방문하는 경우의 수를 생각할 필요가 없는 반면, trap 노드가 추가되면 trap의 상태에 따라 actvie되는 edge에 대한 방문을 수행하고자

이미 최단거리를 구한 노드들을 재방문해야하는 경우의 수가 생긴다.

어떻게 이 복잡한 "trap node" 를 처리해야할까?

 

 

우선 trap노드에 대해 이야기해보자면, trap 노드를 2가지 상태로만 나누어주면 모든 경우의 수를 찾을 수 있다.

trap에 첫번째 방문, 3번째 방문,..... 홀수번째 방문  >> actvie

2번째 방문, 4번째 방문,..... 짝수번째 방문 >> inactive 

2가지 상황으로 나누어보자.

우리가 알아야하는건 결국, 현재 노드에서 어떤 간선을 사용할 수 있는가? 인데 

trap노드는 자신을 가르키는 edge가 trap 노드에 도착하여 active되는 순간 자신이 갈 수 있는 edge로 바뀐다.

따라서 간선 정보를 저장할 때, trap이 active되면 갈 수 있는 간선, 아무런 연관된 노드도 active되어있지 않은 경우로 나누어서 생각해야한다.

 

ex:    a  ->  b    (b는 trap 노드, -> 는 간선)  이런 input이 들어왔다 가정해보자.

기본적으로 a ->b 로 향하는 간선정보를 저장해준다.

하지만 만약 b라는 trap 노드를 방문하게 된다면 어떻게 될까?

b-> a 이런식으로 정보가 바뀌게 될 것이다.

따라서 간선 정보에  시작, 도착 노드외에 추가로 active한 상태를 나타내는 bool 을 한가지 추가해주자.

(true> actvie, false>inactive)

다시 위의 input 예시로 돌아오면,  위의 경우엔   

시작점: a, 도착점:b, 상태: true   라는 정방향 간선 정보와

시작점: b 도착점: a, 상태: false 라는 역방향 간선 정보(trap이 active되었을 시) 를 넣어주면 된다.

 

 

이번엔  간선에 대한 두개의 노드(출발 노드, 도착 노드) 의 상태에 따른 모든 경우의 수를 생각해보자. 

 

trap -> trap  : 

trap이 둘다 active or 둘다 inactive라면 간선이 정방향으로( 두 trap의 상태 정보가 둘 다 true인 간선들만 사용 가능) ,

만약 둘의 상태가 다르다면 역방향 간선이 유효해진다( 두 trap의 상태 정보가 둘 다 false인 간선들만 사용 가능)

 

normal -> normal: 

trap의 active로 인해 간선의 방향이 바뀔일이 없다.   (상태정보가 true인 간선들을 사용가능)

 

trap-> normal or normal-> trap:

trap노드가 active 되어있을 때는 역방향 간선을 사용가능하고(trap의 상태=false)

trap노드가 inactive 되어있다면, 정방향 간선을 사용할 수 있다. (trap의 상태=true)

 

이렇게 경우의 수를 나누어보면, 모든 trap노드들의 상태에 대해서 뒤바뀌는 간선 정보를 올바르게 탐색, 저장할 수 있다.

 

 

그렇다면 위의 정보를 어떻게 우리가 알고 있는 다익스트라 알고리즘에 적용할 수 있을까?

똑같은 노드를 방문하더라도, active되어있는 모든 trap 노드들의 상태에 따라 다른 노드로 취급하면 된다.

 

ex:  3번 노드를 방문할 때, trap 1,2,3 번이 active   <>    3번 노드를 방문할 때  모든 trap이 inactive

 

위 두 상황은 같은 노드를 방문했지만, 분명 서로 다른 결과값을 만들어낼 여지가 존재하고, 그렇기에 두 경우의 수 모두 방문해봐야하는 것이다. 

따라서 기존의 다익스트라가 

 

dist[n] : 시작점에서 n째 노드를 방문하는 최단거리 

     

위의 dp를 사용해 최단 거리를 구하는 것에서 약간 변경하여

 

dist[n][x]: 시작점에서 'x' 상태에 놓인 n째 노드를 방문하는 최단거리.

 

로 변경해주면 된다.

나는 이러한 상태정보를 bit masking을 통해 구현했다.

 

ex: 10 개의 bit값이 각각 active, inactive를 표시한다.  

1111111111    :   모든 trap이 active

000000001   :  마지막 10번째 trap만 active 

 

구현을 어떻게 할지는, 사람에 따라 많이 달라질만한 문제이기에 기본적인 로직만 설명하고 자세한 구현에 대한 설명은 넘어가겠다.

 

* 아래는 작성한 코드인데, 너무 삽질을 많이해서 코드의 상태가 다소 지저분하기에 참고만 해주세요!

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
#define inf 987654321
vector< pair< bool, pair<int,int> > > v[1010];

bool state[1010];
int dist[1010][1025];
int trap_no[1010];
int glob_trap=0<<10;

int trap_state(int state,int num,int to){//현재 state에서 num째 trap을 "to" 상태로.
    if(to==1){
        int n= 1<<num;
        return state|=n;
    }
    else{
        int n= 1<<num;
        return state-=n;
        //return state^=n;
    }
}

int get_trap_state(int state,int num){ //현재 state에서 num번째 trap의 active상태 리턴
    int n=1<<trap_no[num];
    if(n&state) return 1;
    else return 0;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    int answer = 0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<1025;j++){
            dist[i][j]=inf;
        }
    }
    priority_queue<pair<int, pair<int,int> > > pq;
    
   
    
    
    for(int i=0;i<traps.size();i++){
       
        state[traps[i]]=true; //trap or not
        trap_no[traps[i]]=i;
    }
    
    for(int i=0;i<roads.size();i++){
        int st=roads[i][0],ed=roads[i][1],w=roads[i][2];    
        v[st].push_back({true,{w,ed}});// 정방향 edge
        v[ed].push_back({false,{w,st}});// 역방향 edge        
    }
    pq.push({0,{0,start}});
    
    
    while(!pq.empty()){
     
        int ed=pq.top().second.second,w=-pq.top().first;
        int local_state=pq.top().second.first;
        pq.pop(); 
        if(ed==end) { //최단 거리 찾기 완료
            answer=w;
            break;
        }
        if(state[ed]){ //방문 노드가 trap일시 트랩 상태 반전.
            if(get_trap_state(local_state,ed)==1){
                local_state=trap_state(local_state,trap_no[ed],0);
            }
            else if(get_trap_state(local_state,ed)==0){
                local_state=trap_state(local_state,trap_no[ed],1);
            }
        }
        
        
        if(dist[ed][local_state]<w)  continue;
        dist[ed][local_state]=w;
            for(auto e: v[ed]){   // v[st] >> {bool,  {w, ed} }
                //e.first>> treu:정방향 or false: 역방향
                //w: edge의 가중치
                //ed: 현재 노드
                int n_st=ed,n_ed=e.second.second;// 현재 노드, 해당 간선을 통한 다음노드
                if(!state[n_st]&&!state[n_ed]){ //둘다 trap x
                   
                    if(e.first)
                         pq.push({ -(w+e.second.first),{local_state,n_ed} });  
                }
                else if(state[n_st]&&state[n_ed]){// 둘다 trap
                   
                    if(get_trap_state(local_state,n_st)==get_trap_state(local_state,n_ed)){
                   
                        if(e.first){
                            
                             pq.push({ -(w+e.second.first),{local_state,n_ed} });                           }
                    }
                    else if(get_trap_state(local_state,n_st)!=get_trap_state(local_state,n_ed)){
                    
                        if(!e.first){
                            pq.push({ -(w+e.second.first),{local_state,n_ed} });
                           
                        }
                    }
                    
                }
                else if(state[n_st]&&!state[n_ed]){// 둘 중 1개는 trap
                     
                    if(get_trap_state(local_state,n_st)!=1){
                        if(e.first)
                            pq.push({ -(w+e.second.first),{local_state,n_ed} }); 
                    }
                    else{
                        if(!e.first)
                             pq.push({ -(w+e.second.first),{local_state,n_ed} }); 
                           
                    }
                }
                else if(!state[n_st]&&state[n_ed]){// 둘 중 1개는 trap
                    
                     if(get_trap_state(local_state,n_ed)!=1){
                        if(e.first)
                            pq.push({ -(w+e.second.first),{local_state,n_ed} });;  
                    }
                    else{
                        if(!e.first)
                              pq.push({ -(w+e.second.first),{local_state,n_ed} });       
                    }
                }
                    
                
                
            }  
    }
    return answer;
}