[프로그래머스] 2021 카카오인턴십 - 미로탈출 [JAVA]

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/81304

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

오랜만에 알고리즘을 풀었다. 

다익스트라 + 비트마스킹

주석 참조

public static final int INF = Integer.MAX_VALUE;
    public static int maxBit;
    public static Map<Integer,Integer> hm; //좌표압축
    public static int dist[][];
    public static class Node implements  Comparable<Node>{
        int nodeNum;
        int cost;
        int bitmask; // 10개의 트랩에 대해 0~1023
        public Node(){}
        public Node(int a,int b,int c){
            nodeNum = a;
            cost = b;
            bitmask = c;
        }
        public Node(int a,int b){
            nodeNum = a;
            cost = b;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }

    public static ArrayList<Node> forwardList[];
    public static ArrayList<Node> reverseList[];

    public static void init(int N){
        for(int i=1;i<=N;i++){
        	forwardList[i] = new ArrayList<Node>();
            reverseList[i] = new ArrayList<Node>();
            for(int j=0;j<maxBit;j++){
                dist[i][j] = INF;
            }
        }
    }

    public static boolean availForward(int a,int b, int bitmask, int[] traps){
        boolean ret = true;
        int idx = 0;
        while((1<<idx) < maxBit){
            if( ((1<<idx) & bitmask) != 0 ){
                int num = traps[idx];
                if(a == num || b == num){
                    ret ^= true;
                }
            }
            idx++;
        }
        return ret;
    }

    public static int solution(int n, int start, int end, int[][] roads, int[] traps) {
        maxBit = 1 << traps.length;
        hm = new HashMap<Integer,Integer>();
        forwardList = new ArrayList[n+1];
        reverseList = new ArrayList[n+1];
        dist = new int[n+1][1<<traps.length];
        for(int i=0;i<traps.length;i++){
            hm.put(traps[i],i);
        }
        
        init(n);
        
        for(int i=0;i<roads.length;i++){
            int s = roads[i][0];
            int e = roads[i][1];
            int c = roads[i][2];
            forwardList[s].add(new Node(e,c));
            if(hm.containsKey(e) || hm.containsKey(s)){
                reverseList[e].add(new Node(s,c));
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.add(new Node(start,0,0));
        dist[start][0] = 0;
        while(!pq.isEmpty()){
            Node curNode = pq.poll();
            int curNodeNum = curNode.nodeNum;
            int curCost = curNode.cost;
            int curBit = curNode.bitmask;
            if(curNode.nodeNum==end){
                return curCost;
            }
            //정방향 가능한지 ( s->e에서 s,e 중 트랩을 안밟았거나 모두 밟은 경우 )
            for(int i=0;i<forwardList[curNodeNum].size();i++){
                Node next = forwardList[curNodeNum].get(i);
                int nextNodeNum = next.nodeNum;
                int nextCost = curCost + next.cost;
                int nextBit = curBit;
                if(availForward(curNodeNum,nextNodeNum,curBit,traps)){ // 가능한 경우
                    if(hm.containsKey(nextNodeNum)){ //e가 트랩인 경우
                        nextBit ^=(1 << hm.get(nextNodeNum)); 
                    }
                    if(dist[nextNodeNum][nextBit] <= nextCost) continue;
                    dist[nextNodeNum][nextBit] = nextCost;
                    pq.add(new Node(nextNodeNum,nextCost,nextBit));
                }
            }

            //역방향 가능한 지 (s -> e 에서 s,e중 트랩 하나만 밟은 경우)
            for(int i=0;i<reverseList[curNodeNum].size();i++){
                Node next = reverseList[curNodeNum].get(i);
                int nextNodeNum = next.nodeNum;
                int nextCost = curCost + next.cost;
                int nextBit = curBit;
                if(!availForward(curNodeNum,nextNodeNum,curBit,traps)){
                    if(hm.containsKey(nextNodeNum)){//e가 트랩인 경우
                        nextBit ^=(1 << hm.get(nextNodeNum));
                    }
                    if(dist[nextNodeNum][nextBit] <= nextCost) continue;
                    dist[nextNodeNum][nextBit] = nextCost;
                    pq.add(new Node(nextNodeNum,nextCost,nextBit));
                }
            }
        }
        return 0;
    }