#4 미로 탈출
난이도 : LEVEL 4
유형 : 다익스트라 / 비트마스크
코딩테스트 연습 - 미로 탈출
4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4
programmers.co.kr
문제
신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다.
위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다.
출발지점인 1번 방에서 탈출이 가능한 3번 방까지 이동해야 합니다. 탈출하는데 걸리는 최소 시간을 구하려고 합니다.
- 그림의 원은 방을 나타내며 원 안의 숫자는 방 번호를 나타냅니다.
- 방이 n개일 때, 방 번호는 1부터 n까지 사용됩니다.
- 화살표에 표시된 숫자는 방과 방 사이를 이동할 때 걸리는 시간을 나타냅니다.
- 화살표가 가리키고 있는 방향으로만 이동이 가능합니다. 즉, 위 그림에서 2번 방에서 1번 방으로는 이동할 수 없습니다.
- 그림에 표시된 빨간색 방인 2번 방은 함정입니다.
- 함정 방으로 이동하는 순간, 이동한 함정 방과 연결되어있는 모든 길의 방향이 반대가 됩니다.
- 위 그림 1번 방에서 2번 방으로 이동하는 순간 1에서 2로 이동할 수 있던 길은 2에서 1로 이동할 수 있는 길로 바뀌고, 3에서 2로 이동할 수 있던 길은 2에서 3으로 이동할 수 있는 길로 바뀝니다.
- 똑같은 함정 방을 두 번째 방문하게 되면 원래 방향의 길로 돌아옵니다. 즉, 여러 번 방문하여 계속 길의 방향을 반대로 뒤집을 수 있습니다.
- 미로를 탈출하는데 필요한 최단 시간은 다음과 같습니다.
- 1→2: 2번 방으로 이동합니다. 이동 시간은 2입니다.
- 함정 발동: 2번 방과 연결된 모든 길의 방향이 반대가 됩니다.
- 2→3: 3번 방으로 이동합니다. 이동 시간은 3입니다.
- 탈출에 성공했습니다. 총 이동시간은 5입니다.
방의 개수를 나타내는 정수 n, 출발 방의 번호 start, 도착 방의 번호 end, 통로와 이동시간을 나타내는 2차원 정수 배열 roads, 함정 방의 번호를 담은 정수 배열 traps이 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최단 시간을 return 하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ n ≤ 1,000
- 1 ≤ start ≤ n
- 1 ≤ end ≤ n
- 1 ≤ roads의 행 길이 ≤ 3,000
- roads의 행은 [P, Q, S]로 이루어져 있습니다.
- P에서 Q로 갈 수 있는 길이 있으며, 길을 따라 이동하는데 S만큼 시간이 걸립니다.
- 1 ≤ P ≤ n
- 1 ≤ Q ≤ n
- P ≠ Q
- 1 ≤ S ≤ 3,000
- 서로 다른 두 방 사이에 직접 연결된 길이 여러 개 존재할 수도 있습니다.
- 0 ≤ traps의 길이 ≤ 10
- 1 ≤ traps의 원소 ≤ n
- 시작 방과 도착 방은 함정이 아닙니다.
- 항상 미로를 탈출할 수 있는 경우만 주어집니다.
문제 풀이
문제의 본질은 우선순위 큐를 사용한 다익스트라
한 정점(start)에서 다른 정점(end)으로의 최단 경로를 찾는 것이 해당 기본 문제이다. 그러면 베이스로 사용해야할 알고리즘을 BFS나 다익스트라로 좁혀볼 수 있다.
- 서로 다른 두 방 사이에 직접 연결된 길이 여러 개 존재할 수도 있습니다.
조건을 살펴보면 두 정점사이에 여러 개의 간선이 존재할 수 있는데 각 간선에는 가중치가 부여되어있다. 그래서 똑같은 경로라 하더라도 작은 가중치를 가진 간선을 위주로 탐색을 해야하므로 우선순위 큐를 사용한 다익스트라가 문제의 본질임을 알아낼 수 있다.
따라서, 해당 문제는 우선순위 큐를 사용한 다익스트라 문제에 trap이라는 개념만 풀이해주면 된다.
Trap 노드
이제 trap의 성질에 대해 파악을 해보자. trap을 방문하면 trap에 연결되어있는 간선들이 반대 방향으로 바뀌는데 여기서 중요한 점은 각 간선의 상태를 파악하기 위해서 연결된 두 노드의 상태를 모두 파악해줘야 한다는 것이다. 왜냐하면 현재 노드가 trap이 활성화되어 있다고 해서 해당 노드에 연결되어있는 간선들이 모두 역방향으로 전환되어있는 것은 아니기 때문이다.
1) 간선은 현재 하나의 노드가 아닌 연결된 두 노드의 상태에 따라 방향이 결정된다.
역방향을 갖기 위해서는 한쪽 노드의 trap이 활성화되어 있으면 된다. 나머지는 모두 정방향을 갖는다.
→ (1-2), (2-4) 간선은 trap이 활성화된 2번 노드와 연결되어 있어 역방향을 가지고 있다.
→ (2-3) 간선은 반대에 이어져있는 3번 노드의 trap도 활성화되어 있기 때문에 정방향을 가지고 있다.
두 정점의 상태에 따른 간선 방향을 정리하면 다음과 같다.
| 현재 노드 → 다음 노드 | 일반 노드 | 활성화 x 트랩 노드 | 활성화 o 트랩 노드 |
| 일반 노드 | 정방향 (false & false) | 정방향 (false & false) | 역방향 (false & true) |
| 활성화 x 트랩 노드 | - | 정방향 (false & false) | 역방향 (false & true) |
| 활성화 o 트랩 노드 | - | - | 정방향 (true & true) |
2) 비트마스크를 활용한 상태 변화 체크
각 간선은 연결되어있는 두 노드의 상태에 따라 방향이 결정되기 때문에 모든 탐색마다 해당 그래프에 켜져 있는 trap의 상태를 체크해줘야 한다.
- 0 ≤ traps의 길이 ≤ 10
trap의 최대 개수는 10개로 모든 상태를 체크하려면 2^10의 경우의 수를 가진다. 이를 배열로 체크하면 비효율적이기 때문에 비트마스크를 사용해서 trap의 상태를 체크해줄 것이다.
// 배열을 활용한 trap 상태 체크
boolean[] status = { 1, 0 ,1 ,0 ,0 , ... }
// 비트마스크를 활용한 trap 상태 체크
int status = 10100...
시뮬레이션
문제에서 주어진 예제 2번을 시뮬레이션을 돌려보면 trap의 상태와 간선의 방향은 다음과 같이 작동된다. trap status 0은 default이고 10(2)은 1번 노드, 100(2)은 2번 노드를 나타낸다.
+ 추가 설명) 좌표압축 기법
방의 개수는 최대 1000개, 트랩의 최대 10개이다. 그러면 트랩 노드 번호의 간격은 일정하지 않을 것이므로 간단하게 10개의 상태로 나타내기 위해서 좌표압축을 해준다.
trapList = new HashMap<>();
for(int i=0; i<traps.length; i++) {
trapList.put(traps[i], 1<<(i+1)); // 좌표압축
}
좌표 압축 예시) traps : {2, 10 ,15}가 주어졌다면 일반적으로 1, 2, 3으로 저장해주는 것이다.
→ 일반적으로 1, 2, 3이지만 해당 풀이에서는 trap의 상태를 비트마스크를 사용해서 나타낼 것이기 때문에 1<<1 ( = 10(2)), 1<<2 ( = 100(2)), 1<<3 ( = 1000(2))와 같이 비트마스크 형태로 저장해줬다.
풀이 코드
import java.util.*;
class Solution {
static int INF = Integer.MAX_VALUE;
static int[][] dist;
static List<Node>[] list, rList;
static Map<Integer, Integer> trapList;
static class Node implements Comparable<Node>{
int to;
int weight;
int status;
public Node(int to, int weight, int status) {
this.to = to;
this.weight = weight;
this.status = status;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return this.weight - o.weight;
}
}
public int solution(int n, int start, int end, int[][] roads, int[] traps) {
list = new ArrayList[n+1];
rList = new ArrayList[n+1];
for(int i=1; i<n+1; i++) {
list[i] = new ArrayList<>();
rList[i] = new ArrayList<>();
}
// 좌표압축
trapList = new HashMap<>();
for(int i=0; i<traps.length; i++) {
trapList.put(traps[i], 1<<(i+1));
}
for(int i=0; i<roads.length; i++) {
int from = roads[i][0];
int to = roads[i][1];
int w = roads[i][2];
list[from].add(new Node(to,w,0));
rList[to].add(new Node(from,w,0));
}
dist= new int[n+1][1<<trapList.size()+1];
for(int i=0; i<n+1; i++) {
Arrays.fill(dist[i], INF);
}
dijkstra(start, end);
int answer = INF;
for(int ca : dist[end]) {
answer = Math.min(answer, ca);
}
return answer;
}
static void dijkstra(int start, int end) {
Queue<Node> q = new PriorityQueue<>();
dist[start][0] = 0;
q.add(new Node(start,0,0));
while(!q.isEmpty()) {
Node node = q.poll();
int to = node.to;
int w = node.weight;
int status = node.status;
if(to == end) return;
// f1 (start node) 0 = trap x 또는 일반, 1 = trap o
// 현재 트랩 밞은 상태인지 확인 00, 11 : 정방향, 01, 10: 역방향
int f1 = 0;
if(trapList.containsKey(to)) {
if((status & trapList.get(to)) != 0) {
f1 = 1;
}
}
// 정방향 (tt, ff) == 0
int canForward = f1;
for(Node nxt : list[to]) {
canForward = f1;
int nStatus= status;
if(trapList.containsKey(nxt.to)) {
// nxt node 트랩 on 이면 01 = 1 or 11 = 0
if((status & trapList.get(nxt.to)) != 0){
canForward ^= 1;
}
nStatus ^= trapList.get(nxt.to);
}
// 0^0, 1^1
if(canForward == 0) {
if(dist[nxt.to][status] > w + nxt.weight) {
dist[nxt.to][status] = w + nxt.weight;
q.add(new Node(nxt.to, dist[nxt.to][status], nStatus));
}
}
}
// 역방향 (tf, ft) == 1
for(Node nxt : rList[to]) {
canForward = f1;
int nStatus= status;
if(trapList.containsKey(nxt.to)) {
// nxt node 트랩 on 이면 01 = 1 or 11 = 0
if((status & trapList.get(nxt.to)) != 0){
canForward ^= 1;
}
nStatus ^= trapList.get(nxt.to);
}
// 0^1, 1^0
if(canForward ==1) {
if(dist[nxt.to][status] > w + nxt.weight) {
dist[nxt.to][status] = w + nxt.weight;
q.add(new Node(nxt.to, dist[nxt.to][status], nStatus));
}
}
}
}
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
| [BOJ] 백준 1062번 가르침 (Java) (0) | 2021.07.25 |
|---|---|
| [프로그래머스] 2021 카카오 인턴 #5 시험장 나누기 (Java) (0) | 2021.07.25 |
| [프로그래머스] 2021 카카오 인턴 #3 표 편집 (Java) (0) | 2021.07.19 |
| [프로그래머스] 2021 카카오 인턴 #2 거리두기 확인하기 (Java) (0) | 2021.07.18 |
| [프로그래머스] 2021 카카오 인턴 #1 숫자 문자열과 영단어 (Java) (0) | 2021.07.17 |
