프로그래머스 : 미로 탈출

문제유형 : 비트마스크, 다익스트라

 

trap < 10 제한 상황을 통해서 현재 트랩의 모든 겨웅의수는 1024가지 입니다.

 

n값은 1000이므로  [1024][1000] 형태의 다익스트라 digit 값을 만듭니다.

 

이제 각 노드에 방문할 때 현재값이 trap이라면 비트마스크를 이용해서 값을 추가해줍니다.

 

여기서 XOR 연산을 이용한다면 쉽게 트랩의 비트마스클 할 수 있습니다.

 

만약 4개 트랩에 형재 1번째 트랩만 방문한 상태라면

 

0001 형태가됩니다. 이때 2번째 트랩을 방문 했다면 0011 이 되어야하는데

 

0001 ^ 0010 = 0011 로 XOR연산을 할 수 있습니다.

 

마찬가지로 0001 상태에서 또 첫번째 트랩을 방문했다면 0000 이 되어야하는데 

 

0001 ^ 0001 = 0000 인것을 활용하면 쉽게 문제에 접근할 수 있습니다~

 

사실 이문제는 숨겨진 케이스가 존재하는데 예제에는 두노드사이에 길은 단방향으로 하나밖에 안나오지만실제 케이스에는

 

A->B , B->A 두가지가 있습니다.

 

 

import java.util.*;

class Solution {
    static int digit[][];
    static Map<Integer,Integer> hash = new TreeMap<Integer,Integer>();
    static ArrayList[]list;
    
    public int solution(int n, int start, int end, int[][] roads, int[] traps) {
        digit = new int[1<<traps.length][n + 1];
        for(int i=0;i< 1<<traps.length;i++)
            Arrays.fill(digit[i], 987654321);
        
        list = new ArrayList[n + 1];
        
        for(int i=1;i<=n;i++) {
            list[i] = new ArrayList<Edge>();
        }
        
        for(int[] road : roads) {
            int u = road[0];
            int v = road[1];
            int w = road[2];
            list[u].add(new Edge(v,w,0));
            list[v].add(new Edge(u,w,1));
        }
        
        boolean[] visitTraps = new boolean[n + 1];
        
        int count = 0;
        
        for(int trap : traps) {
            hash.put(trap, count++);
            visitTraps[trap] = true;
        }
        
        Solve(n, start, end, visitTraps);
        return answer;
    }
    
    static int answer = 987654321;
    
    static class Three implements Comparable<Three>{
        int v;
        int w;
        int traps;
        
        Three(int v, int w, int traps) {
            this.v = v;
            this.w = w;
            this.traps = traps;
        }
        
        @Override
        public int compareTo(Three o) {
            return this.w - o.w;
        }
    }
    
    static int Solve(int n, int start, int end, boolean[] visitTraps) {
        
        Queue<Three> q = new PriorityQueue<Three>();
        q.add(new Three(start,0,0));
        digit[0][start] = 0;
        
        while(!q.isEmpty()) {
            Three cur = q.poll();
            int u = cur.v;
            int w = cur.w;
            int t = cur.traps;

            if(u == end) {
                answer = Math.min(answer, w);
                continue;
            }
            
            if(visitTraps[u]) {
                int number = hash.get(u);
                t = t ^ (1<<number);
            }
            
            for(Edge next : (ArrayList<Edge>)list[u]) {
                if(check(u,next.v,t)){
                    if(next.state == 0){
                        if(digit[t][next.v] < w + next.w) continue;
                        digit[t][next.v] = w + next.w;
                        q.add(new Three(next.v,w+ next.w, t));                 
                    }
                }else {
                    if(next.state == 1){
                        if(digit[t][next.v] < w + next.w) continue;
                        digit[t][next.v] = w + next.w;
                        q.add(new Three(next.v,w + next.w, t));                 
                    }                    
                }
            }
        }
        
        return -1;
    }
    
    static boolean check(int u, int v, int t) {
        if(!hash.containsKey(u) && !hash.containsKey(v))
            return true;
        
        if(hash.containsKey(u) && hash.containsKey(v)) {
            int uNmuber = hash.get(u);
            int vNumber = hash.get(v);
            
            boolean uForward = (t & (1<<uNmuber)) != (1<<uNmuber);
            boolean vForward = (t & (1<<vNumber)) != (1<<vNumber);
            
            return uForward == vForward ? true : false;
            
        }
        
        if(hash.containsKey(u)) {
            int uNumber = hash.get(u);
            if((t & (1<<uNumber)) == (1<<uNumber))
                return false;
            else 
                return true;    
        }
        
        if(hash.containsKey(v)) {
            int vNumber = hash.get(v);
            if((t & (1<<vNumber)) == (1<<vNumber))
                return false;
            else 
                return true;                
        }
        
        return false;
    }
    
    static class Edge {
        int v;
        int w;
        int state;
        
        Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }
        
        Edge(int v, int w, int state) {
            this.v = v;
            this.w = w;
            this.state = state;
        }
    }
    
    static class Pair {
        int forward;
        int w;
        
        Pair(int forward, int w) {
            this.forward = forward;
            this.w = w ;
        }
    }
}