[2021 카카오 채용연계형 인턴십] Q4. 미로 탈출 (C++, Python, Java)

문제 링크

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

 

예상 난이도

P5

 

알고리즘 분류

다익스트라, 비트마스크

 

풀이

그래프에서의 최단 경로 문제이기에 다익스트라나 플로이드가 쓰일 것으로 유추할 수 있으나 함정의 존재로 인해 그래프의 모양이 계속 달라지는 점이 껄끄럽습니다. 여기서 어떤 관찰을 필요로 하냐면, 함정은 최대 10개이기 때문에 가능한 함정의 on/off 상태는 최대 210개임을 알아차려야 합니다.

 

다익스트라를 생각해보면, 저희는 보통 d[1...n] 테이블을 가지고 다익스트라를 돌렸지만 이번에는 함정의 상태를 감안해 d[1...n][state] 테이블을 가지고 다익스트라를 돌려야 합니다. 이 state는 각 함정 방의 on/off 상태를 비트에 대응시켜서 나타낸 값으로, 비트마스크를 모르면 이해가 아마 힘들 것으로 보입니다. 우선 주어진 그래프로 예를 들면 위의 그림과 같습니다.

 

상태까지 고려했을 때 d[1][00]은 d[2][01]로 전파가 이루어집니다. 2번 방에 도달하는 순간 2번 방이 on되기 때문입니다.

 

나머지 방들도 이렇게 상태를 감안한 간선을 다 연결할 수 있습니다.

 

이후 다익스트라를 이용해 정점과 간선이 최대 1024배 늘어난 그래프에서 d[en][...]으로의 최단 거리를 구하면 됩니다. 저는 구현을 할 때 실제로 각 state에 대응되는 정점을 다 만들어놓는 대신 매번 state를 계산하는 방식으로 구현을 했고, 주석을 나름 친절하게 달려고 노력했으니 자세한건 코드를 확인해주세요.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

int d[1004][1024]; // d[i][state] : (상태 0, start번 노드)에서 (상태 state, i번 노드)로 갈 때의 최단경로 
vector<pair<int,int>> adj[1004]; // 정방향 간선(번호, 시간)
vector<pair<int,int>> adjrev[1004]; // 역방향 간선(번호, 시간)
int trapidx[1004]; // trapidx[i] : i번 노드의 함정 번호. 함정은 0번부터 차례로 번호가 부여되어 있으며 i번 노드가 함정이 아닐 경우 -1

// 상태 state에 i번 비트가 켜져있는지를 반환하는 함수
bool bitmask(int state, int idx){
    return (1 << trapidx[idx]) & state;
}

int solution(int n, int start, int end, vector<vector<int>> roads, vector<int> traps) {
    for(auto road : roads){
        int u = road[0];
        int v = road[1];
        int val = road[2];
        adj[u].push_back({v,val});
        adjrev[v].push_back({u,val});        
    }
    // trapidx 값 지정
    fill(trapidx+1,trapidx+n+1,-1);
    for(int i = 0; i < traps.size(); i++) trapidx[traps[i]] = i;
    for(int i = 1; i <= n; i++) fill(d[i], d[i]+1024,0x7f7f7f7f);
    d[start][0] = 0;
    // priority queue를 작은 원소가 높은 우선순위를 만들게끔 하기 위한 선언
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
    pq.push({d[start][0], start, 0});
    while(!pq.empty()){
        int val, idx, state;
        tie(val, idx, state) = pq.top();
        pq.pop();
        // pq에서 뽑히는 원소는 가까운 순이라는 점을 이용해서 맨 마지막에 d[..][end]를 for문으로 순회하지 않아도 되게 idx1 == end일 때 바로 답을 반환
        if(idx == end) return val;
        if(d[idx][state] != val) continue;
        for(auto p : adj[idx]){ // 정방향 간선에 대한 확인
            int nxt = p.first; // 간선으로 연결된 다음 방
            int dist = p.second;
            int rev = 0;
            if(trapidx[idx] != -1 && bitmask(state, idx)) rev ^= 1; // 현재 idx번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if(trapidx[nxt] != -1 && bitmask(state, nxt)) rev ^= 1; // 현재 nxt번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if(rev) continue; // 정방향 간선을 보고 있으므로 trap을 1개만 밟은 상황일 경우 넘어감
            int nxt_state = state;
            if(trapidx[nxt] != -1) nxt_state ^= (1 << trapidx[nxt]);
            if(d[nxt][nxt_state] > dist + val){
                d[nxt][nxt_state] = dist + val;
                pq.push({d[nxt][nxt_state],nxt,nxt_state});
            }            
        }  

        for(auto p : adjrev[idx]){ // 역방향 간선에 대한 확인
            int nxt = p.first; // 간선으로 연결된 다음 방
            int dist = p.second;
            int rev = 0;
            if(trapidx[idx] != -1 && bitmask(state, idx)) rev ^= 1; // 현재 idx번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if(trapidx[nxt] != -1 && bitmask(state, nxt)) rev ^= 1; // 현재 nxt번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if(!rev) continue; // 역방향 간선을 보고 있으므로 trap을 0개 or 2개 밟은 상황일 경우 넘어감
            int nxt_state = state;
            if(trapidx[nxt] != -1) nxt_state ^= (1 << trapidx[nxt]);
            if(d[nxt][nxt_state] > dist + val){
                d[nxt][nxt_state] = dist + val;
                pq.push({d[nxt][nxt_state],nxt,nxt_state});
            }            
        }
    }
    return -1; // unreachable
}

 

코드(Python)

import heapq

INF = 10**8 + 10
d = [[INF] * 1024 for _ in range(1004)] # d[i][state] : (상태 0, start번 노드)에서 (상태 state, i번 노드)로 갈 때의 최단경로
adj = [[] for _ in range(1004)] # 정방향 간선(번호, 시간)
adjrev = [[] for _ in range(1004)] # 역방향 간선(번호, 시간)
trapidx = [-1] * 1004 # trapidx[i] : i번 노드의 함정 번호. 함정은 0번부터 차례로 번호가 부여되어 있으며 i번 노드가 함정이 아닐 경우 -1

# 상태 state에 i번 비트가 켜져있는지를 반환하는 함수
def bitmask(state, idx):
    return (1 << trapidx[idx]) & state

def solution(n, start, end, roads, traps):
    for u, v, val in roads:
        adj[u].append((v,val))
        adjrev[v].append((u,val))
    
    # trapidx 값 지정
    for i in range(len(traps)):
        trapidx[traps[i]] = i
    
    # dijkstra 진행
    heap = []
    d[start][0] = 0
    heapq.heappush(heap, (d[start][0], start, 0))
    while heap:
        val, idx, state = heapq.heappop(heap)
        # pq에서 뽑히는 원소는 가까운 순이라는 점을 이용해서 맨 마지막에 d[..][end]를 for문으로 순회하지 않아도 되게 idx == end일 때 바로 답을 반환
        if idx == end: return val
        if d[idx][state] != val: continue
        for nxt, dist in adj[idx]: # 정방향 간선에 대한 확인
            rev = 0
            if trapidx[idx] != -1 and bitmask(state, idx): rev ^= 1 # 현재 idx번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if trapidx[nxt] != -1 and bitmask(state, nxt): rev ^= 1 # 현재 nxt번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if rev: continue # 정방향 간선을 보고 있으므로 trap을 1개만 밟은 상황일 경우 넘어감
            nxt_state = state
            if trapidx[nxt] != -1: nxt_state ^= (1 << trapidx[nxt])
            if d[nxt][nxt_state] > dist + val:
                d[nxt][nxt_state] = dist + val
                heapq.heappush(heap, (d[nxt][nxt_state], nxt, nxt_state))
        
        for nxt, dist in adjrev[idx]: # 역방향 간선에 대한 확인
            rev = 0
            if trapidx[idx] != -1 and bitmask(state, idx): rev ^= 1 # 현재 idx번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if trapidx[nxt] != -1 and bitmask(state, nxt): rev ^= 1 # 현재 nxt번 trap을 밟은 상태라면 rev 상태를 뒤집음
            if not rev: continue # 역방향 간선을 보고 있으므로 trap을 0개 or 2개 밟은 상황일 경우 넘어감
            nxt_state = state
            if trapidx[nxt] != -1: nxt_state ^= (1 << trapidx[nxt])
            if d[nxt][nxt_state] > dist + val:
                d[nxt][nxt_state] = dist + val
                heapq.heappush(heap, (d[nxt][nxt_state], nxt, nxt_state))
    
    return -1 # Unreachable

 

코드(Java)

import java.util.*;
class Solution {
    
    class tuple implements Comparable<tuple>{
        int val, idx, state;
        
        public tuple(int val, int idx, int state){
            this.val = val; this.idx = idx; this.state = state;
        }

        @Override
        public int compareTo(tuple o) {
            if (val > o.val) return 1;
            if (val == o.val) return 0;
            return -1;
        }
    }
    
    class pair {
        int x, y;
        pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    final int INF = 0x7f7f7f7f;
    int d[][] = new int[1004][1024]; // d[i][state] : (상태 0, start번 노드)에서 (상태 state, i번 노드)로 갈 때의 최단경로
    List<pair> adj[] = new ArrayList[1004]; // 정방향 간선(번호, 시간)
    List<pair> adjrev[] = new ArrayList[1004]; // 역방향 간선(번호, 시간)
    int trapidx[] = new int[1004]; // trapidx[i] : i번 노드의 함정 번호. 함정은 0번부터 차례로 번호가 부여되어 있으며 i번 노드가 함정이 아닐 경우 -1
    
    // 상태 state에 i번 비트가 켜져있는지를 반환하는 함수
    boolean bitmask(int state, int idx){
        return ((1 << trapidx[idx]) & state) != 0;
    }
    
    public int solution(int n, int start, int end, int[][] roads, int[] traps) {
        // d값을 INF로 초기화
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 1024; j++)
                d[i][j] = INF;
        }
        // adj, adjrev에 대한 초기화
        for(int i = 1; i <= n; i++){
            adj[i] = new ArrayList<>();
            adjrev[i] = new ArrayList<>();            
        }
        // trapidx에 대한 초기화
        for(int i = 1; i <= n; i++) trapidx[i] = -1;
        for(int i = 0; i < traps.length; i++)
            trapidx[traps[i]] = i;
        
        // 통로 처리
        for(int i = 0; i < roads.length; i++){
            int u = roads[i][0];
            int v = roads[i][1];
            int val = roads[i][2];
            adj[u].add(new pair(v, val));
            adjrev[v].add(new pair(u, val));            
        }
        
        d[start][0] = 0;
        PriorityQueue<tuple> pq = new PriorityQueue<>();        
        pq.add(new tuple(d[start][0], start, 0));
        while(!pq.isEmpty()){
            tuple cur = pq.poll();
            // pq에서 뽑히는 원소는 가까운 순이라는 점을 이용해서 맨 마지막에 d[..][end]를 for문으로 순회하지 않아도 되게 idx1 == end일 때 바로 답을 반환
            if(cur.idx == end) return cur.val;
            if(d[cur.idx][cur.state] != cur.val) continue;
            for(int i = 0; i < adj[cur.idx].size(); i++){ // 정방향 간선에 대한 확인
                pair nxt = adj[cur.idx].get(i); // 간선으로 연결된 다음 방
                int rev = 0;
                if(trapidx[cur.idx] != -1 && bitmask(cur.state, cur.idx)) rev ^= 1; // 현재 cur.idx번 trap을 밟은 상태라면 rev 상태를 뒤집음
                if(trapidx[nxt.x] != -1 && bitmask(cur.state, nxt.x)) rev ^= 1; // 현재 nxt.x번 trap을 밟은 상태라면 rev 상태를 뒤집음
                if(rev != 0) continue; // 정방향 간선을 보고 있으므로 trap을 1개만 밟은 상황일 경우 넘어감
                int nxt_state = cur.state;
                if(trapidx[nxt.x] != -1) nxt_state ^= (1 << trapidx[nxt.x]);
                if(d[nxt.x][nxt_state] > nxt.y + cur.val){
                    d[nxt.x][nxt_state] = nxt.y + cur.val;
                    pq.add(new tuple(d[nxt.x][nxt_state], nxt.x, nxt_state));
                }               
            }
            
            for(int i = 0; i < adjrev[cur.idx].size(); i++){ // 역방향 간선에 대한 확인
                pair nxt = adjrev[cur.idx].get(i); // 간선으로 연결된 다음 방
                int rev = 0;
                if(trapidx[cur.idx] != -1 && bitmask(cur.state, cur.idx)) rev ^= 1; // 현재 cur.idx번 trap을 밟은 상태라면 rev 상태를 뒤집음
                if(trapidx[nxt.x] != -1 && bitmask(cur.state, nxt.x)) rev ^= 1; // 현재 nxt.x번 trap을 밟은 상태라면 rev 상태를 뒤집음
                if(rev != 1) continue; // 역방향 간선을 보고 있으므로 trap을 0개 or 2개 밟은 상황일 경우 넘어감
                int nxt_state = cur.state;
                if(trapidx[nxt.x] != -1) nxt_state ^= (1 << trapidx[nxt.x]);
                if(d[nxt.x][nxt_state] > nxt.y + cur.val){
                    d[nxt.x][nxt_state] = nxt.y + cur.val;
                    pq.add(new tuple(d[nxt.x][nxt_state], nxt.x, nxt_state));
                }               
            }
        }
        return -1; // unreachable
    }
}

 

관련 강의

0x1E강 - 다익스트라 알고리즘

  Comments
  • 알린이
    안풀어봤지만, 요즘 코테 난이도 왜이런대요;;
    시험 환경에서 5문제중 플레급 문제를 2개를 풀어내는게 일반적인 코테 준비하는 수준에서 커버가 되는건지 잘모르겠군요..

    심지어 인턴인데... 인턴이라 더 어렵게 낸건가 싶기도하고
댓글 쓰기