[c++][프로그래머스] 미로 탈출

프로그래머스 미로 탈출 [2021 카카오 채용연계형 인턴십]
https://programmers.co.kr/learn/courses/30/lessons/81304

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

문제 풀이

• 이 문제는 BFS + 비트마스킹으로 구현했습니다. 함정의 개수가 최대 10개이기 때문에 함정의 상태를 비트마스킹으로 관리합니다. 
• 함정의 상태에 따라 순방향 or 역방향으로 이동해야하기 때문에 순방향, 역방향 엣지 모두 저장합니다. 

vector<tuple<int,int,bool>> edges[1010];

...

for(auto &r: roads) {
    edges[r[0]].push_back({r[1], r[2], true}); // 순방향
    edges[r[1]].push_back({r[0], r[2], false}); // 역방향
}

• 노드 간에 이동하는 과정에서 현재 노드와 다음 노드의 상태에 따라 순방향으로 이동할지 역방향으로 이동할지 결정해야 합니다. 모든 경우의 수는 다음과 같습니다.
  • cur - next 모두 함정 노드 아닌 경우 -> 순방향
  • cur - next 모두 함정 노드인 경우
    • cur - next 모두 활성화 -> 순방향
    • cur - next 모두 비활성화 -> 순방향
    • cur or next 중 한 쪽만 활성화 -> 역방향
  • cur - next 중 한 쪽이 함정이면서 활성화 -> 역방향
  • 나머지 -> 순방향
• 위의 조건에 맞춰 엣지를 따라 이동하면서 start - end의 최단 시간을 구하면 됩니다.

코드

#include <vector>
#include <unordered_map>
#include <tuple>
#include <queue>

using namespace std;

int dist[1010][1<<10];
unordered_map<int, int> t_idx; // 함정의 index를 저장하기 위한 map

vector<tuple<int,int,bool>> edges[1010];

bool is_trap(int node) {
    return t_idx.find(node) != t_idx.end();
}

// 위에서 설명한 조건에 따라 순방향, 역방향 이동하기 위한 check
bool check(int cur, int next, bool flag, int trap) {
    if(!is_trap(cur) && !is_trap(next)) return flag;
    else if(is_trap(cur) && is_trap(next)) {
        bool flag1 = trap & (1 << t_idx[cur]);
        bool flag2 = trap & (1 << t_idx[next]);

        if(!(flag1 ^ flag2)) return flag;
        else return !flag;
    }
    else if(is_trap(cur) && (trap & 1 << t_idx[cur])) return !flag;
    else if(is_trap(next) && (trap & 1 << t_idx[next])) return !flag;
    else return flag;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    fill(dist[0], dist[0] + (1010 * (1<<10)), 1e7);
    
    for(int i=0; i<traps.size(); ++i) t_idx[traps[i]] = i;
    for(auto &r: roads) {
        edges[r[0]].push_back({r[1], r[2], true});
        edges[r[1]].push_back({r[0], r[2], false});
    }
    
    priority_queue<tuple<int,int,int>> pq;
    
    pq.push({0, 0, start});
    dist[0][0] = 0;
    
    while(!pq.empty()) {
        auto [cost, trap, cur] = pq.top(); pq.pop();
        cost = -cost;
        
        if(cur == end) return cost;
        
        for(auto [next, time, flag]: edges[cur]) {
            if(check(cur, next, flag, trap)) { // 조건에 부합하면 이동
                
                // 다음 노드가 함정이면 활성화시켜줌
                int newState = is_trap(next) ? trap ^ (1 << t_idx[next]) : trap;
                
                if(dist[next][newState] > cost + time) {
                    dist[next][newState] = cost + time;
                    pq.push({-dist[next][newState], newState, next});
                }
            }
        }
    }
    
    return -1;
}

실행 결과