프로그래머스 미로 탈출(81304)

미로 탈출

1. 힌트

1) 정점 개수 $N$ 이 최대 $10^3$인 점에 주목합시다. 함정이 존재하는 방의 개수도 $10$개밖에 안됩니다. 정점의 정의를 조금 변형하면 가중치 그래프에서 언제나 사용하는 다익스트라 알고리즘을 사용할 수 있습니다.

2) 함정 방을 두 번 방문하는 것은 방문하지 않는 것과 같습니다. 따라서 함정 방을 비트마스킹으로 표현하면 $N \times 2^{|traps|}$의 크기로 정점을 정의할 수 있고 이는 $ElogV$의 다익스트라로 충분히 돌아갑니다.

3) 방을 방문할 때 마다 함정 방인지를 확인해서 일일히 간선을 뒤집기보다는 반대 방향 간선을 저장해서 확인해주는 것이 편합니다.(일반 방, 함정 방) $\to$ (일반 방, 함정 방)간의 경우를 잘 처리해 줘야합니다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

그래프에서 간선에 가중치가 있으면 최단 경로는 십중팔구 다익스트라입니다. 그런데 그래프가 좀 특이합니다. 함정 방을 방문할 때마다 간선의 방향이 바뀐다니, 함정 방에 대한 모든 정보를 정점에 포함시켜서 정의할 수 있으면 다익스트라로 처리할 수 있을 것 같습니다. 다행히도 $|traps| \le 10$이므로 비트마스킹으로 정점을 정의할 수 있고, $10^3 \times 2^{10}$개의 정점으로 그래프를 모델링하면 다익스트라로 충분히 가능합니다.

2) 간선의 Case work

어떤 정점을 방문했을 때,
1. 활성화된 트랩인 경우 반대 방향 간선을 확인합니다.
단, 활성화되지 않아야 합니다. 또, 정방향 간선 또한 확인해야 하는데 인접한 정점 또한 활성화되어있다면 간선은 두 번 뒤집혀서 원래대로 돌아오기 때문입니다.

2. 활성화된 트랩이 아닌 경우 정방향 간선을 확인합니다.
   단, 활성화되지 않아야 합니다. 또, 역방향 간선 또한 확인해야하는데 인접한 정좀 또한 활성화되어있다면 이동할 수 있기 때문입니다.

3. 구현

코드가 오른쪽으로 너무 깁니다...
$adj$는 정방향 간선, $adj2$는 역방향 간선을 저장했고, $isTrap[i]$는 $i$번 정점이 함정 방인 경우 몇 번째 함정 방인지(0-based), 함정 방이 아니라면 -1을 저장했습니다. 케이스 워크에 주목해보세요.

class Solution {
    static int N;
    static int[] isTrap;
    static int[] T;
    static ArrayList<ArrayList<Pair>> adj;
    static ArrayList<ArrayList<Pair>> adj2;
    
    static int[][] dijkstra(int src) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        pq.offer(new Pair(src, 0, 0));
        int[][] dist = new int[N + 1][1 << T.length];
        for (int i = 0; i < N + 1; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
        dist[src][0] = 0;
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int here = p.num; int hereTrap = p.trap; int hereCost = p.cost;
            if (dist[here][hereTrap] < hereCost) continue;
            // 활성화 된 트랩인 경우, 
            if (isTrap[here] >= 0 && (hereTrap & (1 << isTrap[here])) > 0) {
                // 활성화되지 않은 역방향 인접한 정점들과
                for (Pair e : adj2.get(here)) if (isTrap[e.num] == -1 || (hereTrap & (1 << isTrap[e.num])) == 0) {
                    int there = e.num; int thereTrap = hereTrap ^ (isTrap[there] >= 0 ? (1 << isTrap[there]) : 0); int thereCost = hereCost + e.cost;
                    if (dist[there][thereTrap] > thereCost) {
                        dist[there][thereTrap] = thereCost;
                        pq.offer(new Pair(there, thereTrap, thereCost));
                    }
                }
                // 활성화 된 정방향 인접한 정점을 확인한다.
                for (Pair e : adj.get(here)) if (isTrap[e.num] >= 0 && (hereTrap & (1 << isTrap[e.num])) > 0) {
                    int there = e.num; int thereTrap = hereTrap ^ (1 << isTrap[there]); int thereCost = hereCost + e.cost;
                    if (dist[there][thereTrap] > thereCost) {
                        dist[there][thereTrap] = thereCost;
                        pq.offer(new Pair(there, thereTrap, thereCost));
                    }
                }
            // 활성화 된 트랩이 아닌 경우
            } else {
                // 활성화된 역방향 인접한 정점을 확인한다.
                for (Pair e : adj2.get(here)) if (isTrap[e.num] >= 0 && (hereTrap & (1 << isTrap[e.num])) > 0) {
                    int there = e.num; int thereTrap = hereTrap ^ (1 << isTrap[there]); int thereCost = hereCost + e.cost;
                    if (dist[there][thereTrap] > thereCost) {
                        dist[there][thereTrap] = thereCost;
                        pq.offer(new Pair(there, thereTrap, thereCost));
                    }
                }
                // 활성화되지 않은 정방향 인접한 정점을 확인한다.
                for (Pair e : adj.get(here)) if (isTrap[e.num] == -1 || (hereTrap & (1 << isTrap[e.num])) == 0) {
                    int there = e.num; int thereTrap = hereTrap ^ (isTrap[there] >= 0 ? (1 << isTrap[there]) : 0); int thereCost = hereCost + e.cost;
                    if (dist[there][thereTrap] > thereCost) {
                        dist[there][thereTrap] = thereCost;
                        pq.offer(new Pair(there, thereTrap, thereCost));
                    }
                }
            }
        }
        return dist;
    }
    
    public int solution(int n, int start, int end, int[][] roads, int[] traps) {
        N = n;
        isTrap = new int[N + 1]; Arrays.fill(isTrap, -1);
        for (int i = 0; i < traps.length; i++) isTrap[traps[i]] = i;
        T = traps;
        adj = new ArrayList<>(N); adj2 = new ArrayList<>(N);
        for (int i = 0; i <= N; i++) { adj.add(new ArrayList<>()); adj2.add(new ArrayList<>()); }
        for (int[] edge : roads) {
            int u = edge[0]; int v = edge[1]; int w = edge[2];
            adj.get(u).add(new Pair(v, w));
            adj2.get(v).add(new Pair(u, w));
        }
        int[][] dist = dijkstra(start);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < (1 << T.length); i++)
            min = Math.min(min, dist[end][i]);
        return min;
    }
    
}

class Pair implements Comparable<Pair> {
    int num, trap, cost;
    
    Pair (int n, int c) { num = n; cost = c; }
    
    Pair (int n, int t, int c) { num = n; trap = t; cost = c; }
    
    @Override
    public int compareTo(Pair o) { return cost - o.cost; }
}

1) 시간 복잡도

간선을 두 번씩 확인하지만 여전히 다익스트라의 시간 복잡도와 동일합니다 $O(ElgV)$입니다.