[틀림] 프로그래머스 미로탈출 // 상태기반 다익스트라, 비트마스킹을 이용한 다익스트라

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

프로그래머스

 

* 시도1

trap을 만날때마다, 실제로 그래프를 수정해주는 방법

실패

import java.util.*;

public class A{
    int node;
    int weight;
    int state; //trap이 발동되었는지
    A(int node, int weight, int state){
        this.node=node;
        this.weight=weight;
        this.state=state;
    }
    
    public String toString(){
        return "노드: " + this.node + ", 가중치: " + this.weight;
    }
}

class Solution {
    
    static int[] dist = new int[1004];
    static ArrayList<A>[] adj = new ArrayList[1004];
    static int[][] graph = new int[1004][1004];
    static PriorityQueue<A> pq= new PriorityQueue<>((a,b) -> a.weight-b.weight);
    int ret;
    
    boolean isTrap(int x, int[] traps){
        for(int trap : traps){
            if(x==trap) return true;
        }
        return false;
    }
    
    public int solution(int n, int start, int end, int[][] roads, int[] traps) {
        Arrays.fill(dist,Integer.MAX_VALUE);
        
        
        for(int i=0;i<1004;++i){
            for(int j=0;j<1004;++j){
                if(i==j){
                    graph[i][j]=Integer.MAX_VALUE; //자기자신은 못감?
                }
                else{
                    graph[i][j]=Integer.MAX_VALUE;
                }
            }
        }
        
        for(int [] road : roads){
            int u = road[0];
            int v = road[1];
            int w = road[2];
            graph[u][v]=w;
        }
        
        dist[start]=0;
        pq.offer(new A(start,0));
        // System.out.println(pq);
        while(pq.size()>0){
            A a = pq.poll();
            int cur = a.node;
            int weight=a.weight;
            System.out.println(cur+" "+weight);
            
            //cur이 trap인경우
            if(isTrap(cur,traps)){
                //trap -> nxt 검사
                for(int nxt=1;nxt<1004;++nxt){
                    if(graph[cur][nxt]==Integer.MAX_VALUE) continue;
                    int tmp = graph[cur][nxt];
                    graph[cur][nxt]=Integer.MAX_VALUE;
                    graph[nxt][cur]=tmp;
                }
                //nxt -> trap 검사
                for(int nxt=1;nxt<1004;++nxt){
                    if(graph[nxt][cur]==Integer.MAX_VALUE) continue;
                    int tmp = graph[nxt][cur];
                    graph[nxt][cur]=Integer.MAX_VALUE;
                    graph[cur][nxt]=tmp;
                }
            }
            
            //cur과 연결된 nxt 찾기
            for(int nxt=1;nxt<1004;++nxt){
                if(graph[cur][nxt]==Integer.MAX_VALUE) continue;
                if(dist[nxt] > dist[cur] + graph[cur][nxt]){
                    dist[nxt] = dist[cur] + graph[cur][nxt];
                    pq.offer(new A(nxt,dist[nxt]));
                }
            }
        
        }
        
        // for(int i=1;i<=n;++i){
        //     System.out.println(dist[i]);
        // }
        return dist[end];
    }
}

 

* 풀이

dist[i][j] : start 부터 i까지 가는데 최단거리, trap 상태가 j일때

trap이 (cur, nxt)가 둘중 하나만 켜진경우, 방향이 바뀐다는 점을 알아내야 함.

작동과정

1. 인접행렬 만들기, 역방향-순방향 2개 만들기, 간선이 여러개인경우 대비 -> 최소값으로 넣기

2. 인접행렬은 next를 찾기위해 완탐필요

3. cur이 trap상태가 켜졌는지 검사

4. nxt도 trap상태가 켜졌는지 검사

5. 둘중 하나만 켜진경우, 리버스를 참조해서 weight를 구하기, 아니면 정방향을 참조해서 wieght구하기

6. weight가 무한대면 갈수없음

7. nxt가 트랩인경우, 다음상태 = 현재상태 ^ (1<<nxt trap idx) // 해당비트만 토글해주기

8. dist갱신, pq에 넣기

 

import java.util.*;

public class A {
    int node;
    int weight;
    int state; // 트랩 상태를 저장

    A(int node, int weight, int state) {
        this.node = node;
        this.weight = weight;
        this.state = state;
    }
    
    @Override
    public String toString() {
        return "노드: " + this.node + ", 가중치: " + this.weight + ", 상태: " + this.state;
    }
}

class Solution {
    
    // 트랩인지 확인하는 메소드
    boolean isTrap(int node, int[] traps) {
        for (int trap : traps) {
            if (node == trap) return true;
        }
        return false;
    }
    
    // 트랩의 인덱스를 찾는 메소드
    int getTrapIndex(int node, int[] traps) {
        for (int i = 0; i < traps.length; i++) {
            if (node == traps[i]) return i;
        }
        return -1;
    }
    
    public int solution(int n, int start, int end, int[][] roads, int[] traps) {
        // 트랩의 최대 개수 (최대 10개로 가정)
        int maxTraps = traps.length;
        int maxStates = 1 << maxTraps; // 모든 트랩 상태의 조합 (2^maxTraps)
        
        // 거리 배열: [노드][상태]
        int[][] dist = new int[n + 1][maxStates];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        // 그래프 초기화
        int[][] normalGraph = new int[n + 1][n + 1]; // 정방향 간선
        int[][] reverseGraph = new int[n + 1][n + 1]; // 역방향 간선
        
        for (int i = 0; i <= n; i++) {
            Arrays.fill(normalGraph[i], Integer.MAX_VALUE);
            Arrays.fill(reverseGraph[i], Integer.MAX_VALUE);
        }
        
        // 간선 정보 추가
        for (int[] road : roads) {
            int u = road[0];
            int v = road[1];
            int w = road[2];
            
            // 더 작은 가중치 선택
            normalGraph[u][v] = Math.min(normalGraph[u][v] == Integer.MAX_VALUE ? w : normalGraph[u][v], w);
            reverseGraph[v][u] = Math.min(reverseGraph[v][u] == Integer.MAX_VALUE ? w : reverseGraph[v][u], w);
        }
        
        // 다익스트라 알고리즘
        dist[start][0] = 0;
        PriorityQueue<A> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        pq.offer(new A(start, 0, 0));
        
        while (!pq.isEmpty()) {
            A current = pq.poll();
            int curNode = current.node;
            int curWeight = current.weight;
            int curState = current.state;
            
            System.out.println(curNode+" "+curWeight+" "+curState);
            
            // 현재 상태에서의 최단 거리가 아니면 스킵 (느긋한 삭제)
            if (dist[curNode][curState] != curWeight) continue;
            
            // 목적지에 도달했으면 종료
            // pq에서 뽑히는 원소는 가까운 순이라는 점을 이용해서 맨 마지막에 d[end][..]를 
            // for문으로 순회하지 않아도 되게 idx1 == end일 때 바로 답을 반환
            if (curNode == end) return curWeight;
            
            // 현재 노드와 연결된 모든 노드 확인
            for (int nextNode = 1; nextNode <= n; nextNode++) {
                if (curNode == nextNode) continue; // 자기 자신으로 가는 경우 제외
                
                // 대상 : 모든노드, weight를 보고 연결됬는지 나중에 판단!
                // 현재 노드와 다음 노드의 트랩 상태 확인
                // 노드가 트랩인지 && 현재 상태에서 해당 트랩이 활성화되었는지
                boolean curNodeTrapped = isTrap(curNode, traps) && 
                    ((curState & (1 << getTrapIndex(curNode, traps))) != 0);
                boolean nextNodeTrapped = isTrap(nextNode, traps) && 
                    ((curState & (1 << getTrapIndex(nextNode, traps))) != 0);
                
                // 간선 방향 결정
                boolean isReversed = curNodeTrapped ^ nextNodeTrapped;
                int weight = isReversed ? reverseGraph[curNode][nextNode] : normalGraph[curNode][nextNode];
                
                if (weight == Integer.MAX_VALUE) continue; // 해당 방향으로 간선이 없음
                
                // 다음 상태 계산 (트랩 방문 시 상태 토글)
                int nextState = curState;
                if (isTrap(nextNode, traps)) {
                    nextState ^= (1 << getTrapIndex(nextNode, traps)); // 해당 트랩 비트 토글
                }
                
                // 더 짧은 경로 발견 시 갱신
                if (dist[nextNode][nextState] > dist[curNode][curState] + weight) {
                    dist[nextNode][nextState] = dist[curNode][curState] + weight;
                    pq.offer(new A(nextNode, dist[nextNode][nextState], nextState));
                }
            }
        }
        
        // 목적지에 도달할 수 없는 경우
        return -1;
    }
}