<Lv.4> 미로 탈출 (프로그래머스 : C#)

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

📕 문제 설명

방들이 존재하고 이동에 걸리는 시간이 있으며 함정이 존재한다. 주어진 방향으로만 움직일 수 있으며 함정을 밟으면 방향이 반대로 바뀐다. 이때 출발 방부터 도착 방까지 걸리는 최단 시간 구하기

• Input
  방의 개수 n, 출발 방 번호 start, 도착 방 번호 end, 통로 이동시간 정보 roads, 함정 방 번호 traps

• Output
  미로 탈출에 필요한 최단 시간

예제

풀이

비트 마스크와 다익스트라를 기반으로 풀었다. 함정 상태를 비트 마스크로 나타내 길을 갈 수 있는 케이스만 우선 순위 큐에 넣어 최단 거리를 뽑는 식으로 진행

1) 방문 여부 확인용 vistied [함정 상태, 노드 번호]
2) 압축된 함정 정보 (노드 index => trap의 index)

• 예를 들어 노드 5, 10이 trap이면 각각 0, 1로 만드는 것

3) graph 초기화 [다음 노드, 비용, 도로 방향 (정방향, 역방향)]

• 초기화 할 때 road 정보를 기반으로 기본 방향은 도로 방향에 0을, 도착 노드와 출발 노드 거꾸로 한 정보는 도로 방향에 1을 넣어 초기화해준다.

4) 최소 힙 (Node => 비용, 현재 노드 번호, 함정 상태)

• 마지막으로 최소 힙에서 나온 현재 노드와 해당 노드의 다음 노드 (그래프 순회)의 상태에 따라 도로를 건널 수 있는 상황인지 판단하고 최소 힙에 다음 정보 넣을 여부 결정

• 현재 노드와 다음 노드의 경우 다음 상태를 가진다.

현재 노드	다음 노드
일반	일반
일반	함정
함정	일반
함정	함정

• 노드의 상태에 따라 도로 방향이 결정된다. 발동된 함정의 개수를 생각하면 되는데 함정이 홀수 횟수로 발동되면 역방향이, 짝수 횟수면 정방향이다. 이를 고려해서 상태에 따라 다음과 같은 경우 도로를 건널 수 없는 케이스가 된다.

1) 두 노드 모두 일반 && 도로 방향 역방향
2) 두 노드 중 하나 함정 && (함정 발동 여부 != 도로 방향)
3) 두 노드 모두 함정 && (함정 발동 개수 % 2 != 도로 방향)
(+ 개수로 판단해도 되고 xor 연산해서 두 함정의 발동 여부가 동일한지를 확인해도 된다.)

위 세 케이스를 제외하고 최소 힙에 넣어가면서 최종 end 노드를 만나게 되면 cost를 반환하면 답이 나오게 된다.

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int n, int start, int end, int[,] roads, int[] traps) {
        int answer = 0;
        
        List<(int, int, int)>[] graph = new List<(int, int, int)>[n+1];
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List<(int, int, int)>();
        }
        // 그래프 정보 초기화 (다음 노드 번호, 도로 이동 시간, 도로 방향)
        for (int i = 0; i < roads.GetLength(0); i++)
        {
            int departNode = roads[i,0];
            int arrivalNode = roads[i,1];
            int cost = roads[i,2];
            
            graph[departNode].Add((arrivalNode, cost, 0)); // 0 = 정방향
            graph[arrivalNode].Add((departNode, cost, 1)); // 1 = 역방향
        }
        
        bool[,] visited = new bool[(1 << traps.Length), n+1]; // 방문 여부 확인용 (trap상태, trap 번호)
        Dictionary<int, int> compactedTraps = new Dictionary<int, int>(); // 노드 번호 상관없이 trap기준 index매기는용
        for (int i = 0; i < traps.Length; i++)
        {
            compactedTraps[traps[i]] = i;
        }
        
        PriorityQueue pq = new PriorityQueue();
        pq.Enqueue(new Node() {cost = 0, index = start, trapState = 0});
        
        while (pq.Count >= 1)
        {
            Node node = pq.Dequeue();
            int currNode = node.index;
            int currTrapState = node.trapState;
            if (currNode == end) return node.cost;
            if (visited[currTrapState, currNode]) continue;
            visited[currTrapState, currNode] = true;
            
            foreach(var nextNodes in graph[currNode])
            {
                int nextNode = nextNodes.Item1;
                int nextCost = nextNodes.Item2;
                int roadType = nextNodes.Item3;
                 
                bool isCurrNodeTrap = compactedTraps.ContainsKey(currNode);
                bool isNextNodeTrap = compactedTraps.ContainsKey(nextNode);
                
                // case1) 두 노드 모두 함정이 아닌경우
                if (isCurrNodeTrap == false && isNextNodeTrap == false)
                {
                    if (roadType == 1) continue; // 역방향인 경우 길 없음
                }
                
                // case2) 두 노드 모두 함정인 경우
                else if (isCurrNodeTrap == true  && isNextNodeTrap == true)
                {
                    // 각 함정 발동 여부
                    int isCurrTrapActivated = (currTrapState & (1 << compactedTraps[currNode])) >> (compactedTraps[currNode]);
                    int isNextTrapActivated = (currTrapState & (1 << compactedTraps[nextNode])) >> (compactedTraps[nextNode]);
                    // 두 노드 함정 발동 여부 같은 경우 (정방향) (즉, 발동 개수가 짝수개)
                    // => 두 노드 함정 발동 여부 다른 경우 (역방향) (즉, 발동 개수가 홀수개)
                    if (((isCurrTrapActivated + isNextTrapActivated) % 2) != roadType) continue;
                }
                
                // case 3) 두 노드 중 하나만 함정
                else
                {
                    int trapNode = isCurrNodeTrap ? currNode : nextNode;
                    int isTrapActivated = (currTrapState & (1 << compactedTraps[trapNode])) >> (compactedTraps[trapNode]);
                    // 함정 발동된 경우 => 역방향, 발동 x => 정방향
                    if (isTrapActivated != roadType) continue;
                }
                
                // 다음 노드 함정이면 state udpate해서 힙에 넣기
                int nextState = currTrapState;
                if (isNextNodeTrap)
                {
                    nextState  = currTrapState ^ (1 << compactedTraps[nextNode]);
                }
                
                pq.Enqueue(new Node {cost = node.cost + nextCost, index = nextNode, trapState = nextState});
            }
        }
        
        
        return answer;
    }
}

public struct Node
{
    public int cost;
    public int index;
    public int trapState;
}

public class PriorityQueue
{
    List<Node> heap = new List<Node>();
    public int Count => heap.Count;
    
    public void Enqueue(Node data)
    {
        heap.Add(data);
        int now = heap.Count - 1; // 추가한 노드 위치 (트리 마지막 레벨 왼쪽)
        
        while (now > 0) // 순서 지정하기
        {
            int next = (now - 1) / 2; // 부모 노드 (트리)
            if (heap[now].cost > heap[next].cost) break;
            // 부모노드보다 추가한게 작으면 Swap
            Node temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            now = next;
        }
    }
    
    public Node Dequeue()
    {
        Node ret = heap[0]; // return할 값 (트리 root에 max 저장해둔 형태)
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        lastIndex -= 1;
        int now = 0;
        
        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;
            int next = now;
            
            if (left <= lastIndex && heap[next].cost > heap[left].cost) next = left; // 왼쪽보다 크면 왼쪽으로 보내기
            if (right <= lastIndex && heap[next].cost > heap[right].cost) next = right; // 오른쪽보다 크면 오른쪽으로 보내기 (여기서는 위에 now랑 left랑 비교해서 더 큰애랑 또 비교해서 갱신하게됨)
            if (next == now) break;
            
            Node temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            
            now = next;
        }
        
        return ret;
        
    }
}

결과