```java
import java.util.*;
public class Solution {
private static final int INF = Integer.MAX_VALUE / 2;
public class Node {
int number;
int cost;
int state; // 비트마스크 (ex. 001이면 0,1번 트랩은 비활성 2번 트랩은 활성이라는 뜻!)
public Node(int number, int cost, int state) {
this.number = number;
this.cost = cost;
this.state = state;
}
}
public int solution(int n, int start, int end, int[][] roads, int[] traps) {
int[][] graph = new int[n + 1][n + 1];
for(int i = 0; i <= n; ++i) {
Arrays.fill(graph[i], INF);
graph[i][i] = 0;
}
for(int[] road : roads) {
graph[road[0]][road[1]] = Math.min(graph[road[0]][road[1]], road[2]);
}
boolean[][] visited = new boolean[n + 1][1 << traps.length]; // 트랩의 길이만큼 비트 마스크 초기화
PriorityQueue queue = new PriorityQueue<>((a, b) -> a.cost - b.cost);
queue.add(new Node(start, 0, 0));
while (!queue.isEmpty()) {
Node current = queue.poll();
int state = current.state;
if(current.number == end) return current.cost;
if(visited[current.number][current.state]) continue;
visited[current.number][current.state] = true;
boolean currentTrapped = false;
Set trapped = new HashSet<>();
for(int i = 0; i < traps.length; i++) {
int bit = 1 << i;
if((state & bit) != 0) { // trap이 현재 활성 상태인 경우
if(current.number == traps[i]) { // 그 트랩이 현재 노드인 경우에는 비활성화 (방문을 했기 때문)
state &= ~bit;
continue;
}
trapped.add(traps[i]);
continue;
}
if (current.number == traps[i]) { // 비트에 해당하는 trap이 활성 상태가 아니고, 그 트랩이 현재 노드인 경우 활성화 (방문을 했기 때문)
state |= bit;
trapped.add(traps[i]);
currentTrapped = true;
}
}
for (int next = 1; next <= n; next++) {
if(current.number == next) continue;
if(graph[current.number][next] == INF && graph[next][current.number] == INF) continue; // 아예 연결되어 있지 않으면 Skip!
boolean nextTrapped = trapped.contains(next); // 다음 이동할 노드가 trap인지 체크
if (currentTrapped == nextTrapped) { // 현재 노드, 다음 노드 둘다 트랩이거나, 둘 다 아니거나는 결과가 동일
if(graph[current.number][next] != INF) {
queue.add(new Node(next, current.cost + graph[current.number][next], state));
}
continue;
}
// 둘 중 하나가 트랩이라면 그래프의 역방향을 적용
if (graph[next][current.number] != INF) {
queue.add(new Node(next, current.cost + graph[next][current.number], state));
}
}
}
return INF;
}
}
```
코멘트
- 다익스트라 응용 같아 보이긴 했는데.. 어렵네요😭 경로마다 트랩 상태를 저장하고, 트랩 상태가 다를 때는 계속 탐색하도록 해야 하는데, 여기에 비트 마스크를 써야 했네요..! 비트 마스크는 약한데 공부해야 겠습니다ㅜㅜ
uijin-j
commented
1 month ago
🔗 미로 탈출