IT recording...
[PG] 미로탈출 - Java 본문
https://programmers.co.kr/learn/courses/30/lessons/81304?language=java
코딩테스트 연습 - 미로 탈출
4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4
programmers.co.kr
[풀이]
1. 단일 노드에서 단일 노드로 가는 최단 거리를 구하는 문제 => 다익스트라
아니 근데! Trap이라는 요소가 추가되었다.
같은 노드까지 간 경우라고 하더라도, 존재하는 trap중에 어떤것들이 밟혔는지에 따라 길이 달라진다.
따라서 보통은 다익스트라에서 dist[노드] 로 노드만 고려해주지만, dist[노드][trap들이 밟힌 경우] 로 한다.
2. map 전체에서 trap들이 밟힌 경우는 boolean배열을 사용할 수도 있다. 하지만, 문제에서 주어진 Trap의 최대 갯수는 10개인데 밟히고,안밟힌 모든 경우의 수를 표현하기 위해서는 2^10 의 공간이 필요하다. 따라서 비트마스킹을 사용하자
//1번 노드가 밟힌 경우
1<<1 //1
//3번 노드가 밟힌 경우
1<<3 //1003. 정방향인지 역방향인지는 현재 있는 노드와, 다음에 갈 노드의 콜라보레이션~으로 구할 수 있다.
현재 있는 노드를 now, 다음 노드를 next라고 하고, 밟힌 경우를 true(1), 아닌 경우를 false(0)라고 해보자.
| now | next | 정방향(0), 역방향(1) |
| 0 | 0 | 0 //둘 다 꺼져있음 |
| 0 | 1 | 1 //둘 중 하나만 밟혀있음 |
| 1 | 0 | 1 //둘 중 하나만 밟혀있음 |
| 1 | 1 | 0 //둘 다 켜져있음 |
어디선가 많이 본 연산일 것이다. 바로 XOR!
1) 그래서 현재 now가 켜져있는지 확인하고 (curTrapped),
boolean currTrapped = false;
if(TrapHashMap.containsKey(middle)){ //지금 밟은게 trap인지 확인
//전체적인 상황이랑 & 지금 밟고 있는게 trap인지 -> 지금 밟고 있는게 trap이 켜져있음
if(((mapStatus) & TrapHashMap.get(middle)) != 0){
currTrapped = true;
}
}-> 확인하는 연산은 지금 밟은 바로 이 노드가 현재 mapStatus중에서 켜져있는지를 보는 것이다.
ex)
지금 mapStatus가 1,3번이 밟혀있는 상황이라면 mapStatus = 101(2진수표기법) 일 것이다.
현재 밟은 노드가 3번 이라고 할 때 trap이면 TrapHashMap.get(3) = 100(2진수표기법)
=> 지금 밟은 3번 노드가 밟혀져있는지를 보고 싶은 것이므로 101중에 3번 노드가 켜져있는지를 확인하면 된다.
따라서 101 & 100 = 100 -> 3번에 해당하는 부분을 map에 있는지 and연산을 했는데 결과값이 0이 아니면 밟혀있는것, 0이면 안밟혀있는 것이라고 할 수 있다.
2) next가 켜져있는지 확인하고 (nextTrapped), canForward = currTrapped ^ nextTrapped로 정방향인지 역방향인지 , 즉 갈 수 있는지를 확인한다.
if(TrapHashMap.containsKey(end)){ //다음꺼가 trap인지 확인
//전체적인 상황이랑 & 다음이 trap인지 -> 다음 trap이 켜져있음
if(((mapStatus) & TrapHashMap.get(end)) != 0){
nextTrapped = true;
}
newMapStatus ^= TrapHashMap.get(end); //다음이 trap이면 밟은 상태로 업데이트
}
canForward = currTrapped ^ nextTrapped;3)lList(정방향 리스트)를 보고 있는 경우 false(0)이 나오면 다익스트라 갱신을 진행하고,
rList(역방향 리스트)를 보고 있는 경우 true(1)가 나오면 다익스트라 갱신을 진행한다.
4. 다익스트라 갱신을 진행할 때 주의할 점이 있다.
[보통 다익스트라 갱신 방법]
* 보통은 startToMiddleToEnd = dist[middle] + next.weight 와 같이 그냥 노드 값만으로 이전까지의 최단거리를 참조해서 썼었다.
하지만 이 문제는 노드만을 고려하는 것이 아니라, 밟혔는지의 비트도 함께 고려해야 한다.
int nextEnd =next.end;
int rootToMiddleToEnd = dist[middle] + next.weight; //root > middle > end 새로운것
int rootToEnd = dist[nextEnd]; //root > end 기존것
//새로운것이 더 작으면 갱신
if(rootToMiddleToEnd < rootToEnd){ //여러개의 최단 경로를 고려할 경우 등호를 넣어준다.
dist[nextEnd] = rootToMiddleToEnd;
queue.add(new Info(nextEnd,dist[nextEnd])); //큐에 넣기
}[이 문제에서의 갱신 방법]
1. 우선, dist배열 자체의 갱신은 다음에 진행할 노드(next)가 밟혀져있는지 아닌지와는 상관없다.
현재 존재하는 노드(now)에서 다음 노드로 진행하고자 할 때는 다음 노드를 밟은 상태가 아니기 때문이다.
따라서 dist[next][밟기전맵상태] 로 dist를 업데이트한다.
2. 하지만 다음 노드(next)를 간 상태도 기록해주긴 해야한다. 따라서 맵의 상태는 newMapStatus로 갱신해서 함께 넘겨준다.
3. 그렇다면 startToMiddleToEnd = dist[middle][mapStatus] + next.weight 를 사용해도 될까? 답은 No다.
갱신을 진행할 때 dist는 밟기 전 상태(mapStatus)(A)로 갱신을 했고, 다음 노드의 상태는 newMapStatus(B)로 넘겨준다.
그래서 다음 노드에서 다익스트라 갱신을 진행할 때의 mapStatus는 사실 이전 갱신때의 newMapStatus(B)와 같기 때문에
dist[middle][mapStatus(B)] 와 같이 사용한다면 이전에 갱신해준 값(dist[middle][(A)])을 사용하지 못하게 된다.
따라서 dist[middle][A]를 사용하도록 하기 위해서 이 값을 함께 큐에 넣어주게 되고,
int w = now.weight; //이전에 갱신한 dist[end][A] 값로 받아서 startToMiddleToEnd = w + next.weight 를 하는 것이다.
if(!canForward){
//다익스트라 진행
int startToMiddleToEnd = w + next.weight;
int startToEnd = dist[end][mapStatus];
if(startToMiddleToEnd<startToEnd){
dist[end][mapStatus] = startToMiddleToEnd;
queue.add(new Node(end,dist[end][mapStatus],newMapStatus)); //원래는 dist[새로운거] 가 들어가지만 여기서는 새로운 노드 + 아직 다음꺼가 안 밟힌 상태를 전달해줘야해서 이렇게 전달
}
}
[코드]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
public class Pg_미로탈출 {
public static void main(String[] args) throws Exception{
//input
int n=3;
int start=1;
int end=3;
int[][] roads={{1,2,2},{3,2,3}};
int[] traps={2};
int answer = Solution.solution(n,start,end,roads,traps);
System.out.println(answer);
}
static class Solution {
static ArrayList<Node>[] lList,rList;
static int N,End;
static int answer = Integer.MAX_VALUE;
static HashMap<Integer,Integer> TrapHashMap = new HashMap<>();
static int[][] dist;
static int INF = Integer.MAX_VALUE;
public static int solution(int n, int start, int end, int[][] roads, int[] traps) {
N = n;
End = end;
lList = new ArrayList[n+1];
rList = new ArrayList[n+1];
for(int i=1;i<n+1;i++){
lList[i] = new ArrayList<>();
rList[i] = new ArrayList<>();
}
for(int i=0;i<roads.length;i++){
int P = roads[i][0];
int Q = roads[i][1];
int S = roads[i][2];
lList[P].add(new Node(Q,S,0)); //P->Q, S만큼 가중치
rList[Q].add(new Node(P,S,0));
}
for(int i=0;i<traps.length;i++){
int trap = traps[i];
TrapHashMap.put(trap,1<<(i+1));
}
dist = new int[n+1][1<<TrapHashMap.size()+1]; //node이면서, trap이 어디가 켜져있는지 봅시다
for(int i=1;i<n+1;i++){
Arrays.fill(dist[i],INF);
}
dijkstra(start);
for(int val:dist[End]){
answer = Math.min(answer,val);
}
return answer;
}
static void dijkstra(int start){
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(start,0,0));
dist[start][0] = 0;
while(!queue.isEmpty()){
Node now = queue.poll();
int middle = now.end;
int w = now.weight;
int mapStatus = now.status;
if(middle==End){ //도착지에 도착
return;
}
boolean currTrapped = false;
if(TrapHashMap.containsKey(middle)){ //지금 밟은게 trap인지 확인
//전체적인 상황이랑 & 지금 밟고 있는게 trap인지 -> 지금 밟고 있는게 trap이 켜져있음
if(((mapStatus) & TrapHashMap.get(middle)) != 0){
currTrapped = true;
}
}
//정방향 -> currTrapped ^ nextTrapped == false
//lList 돌면서 정방향인 애들 큐에 넣기
boolean nextTrapped = false;
boolean canForward = false;
for(Node next: lList[middle]){
int end = next.end;
nextTrapped = false; //초기화
int newMapStatus = mapStatus;
if(TrapHashMap.containsKey(end)){ //다음꺼가 trap인지 확인
//전체적인 상황이랑 & 다음이 trap인지 -> 다음 trap이 켜져있음
if(((mapStatus) & TrapHashMap.get(end)) != 0){
nextTrapped = true;
}
newMapStatus ^= TrapHashMap.get(end); //다음이 trap이면 밟은 상태로 업데이트
}
canForward = currTrapped ^ nextTrapped;
if(!canForward){
//다익스트라 진행
int startToMiddleToEnd = w + next.weight;
int startToEnd = dist[end][mapStatus];
if(startToMiddleToEnd<startToEnd){
dist[end][mapStatus] = startToMiddleToEnd;
queue.add(new Node(end,dist[end][mapStatus],newMapStatus)); //원래는 dist[새로운거] 가 들어가지만 여기서는 새로운 노드 + 아직 다음꺼가 안 밟힌 상태를 전달해줘야해서 이렇게 전달
}
}
}
//역방향
//rList 돌면서 역방향인 애들 큐에 넣기
nextTrapped = false;
canForward = false;
for(Node next: rList[middle]){
int end = next.end;
nextTrapped = false; //초기화
int newMapStatus = mapStatus;
if(TrapHashMap.containsKey(end)){ //다음꺼가 trap인지 확인
//전체적인 상황이랑 & 다음이 trap인지 -> 다음 trap이 켜져있음
if(((mapStatus) & TrapHashMap.get(end)) != 0){
nextTrapped = true;
}
newMapStatus ^= TrapHashMap.get(end); //다음이 trap이면 밟은 상태로 업데이트
}
canForward = currTrapped ^ nextTrapped;
if(canForward){
//다익스트라 진행
int startToMiddleToEnd = w + next.weight;
int startToEnd = dist[end][mapStatus];
if(startToMiddleToEnd<startToEnd){
dist[end][mapStatus] = startToMiddleToEnd;
queue.add(new Node(end,dist[end][mapStatus],newMapStatus)); //원래는 dist[새로운거] 가 들어가지만 여기서는 새로운 노드 + 아직 다음꺼가 안 밟힌 상태를 전달해줘야해서 이렇게 전달
}
}
}
}
}
static class Node implements Comparable<Node>{
int end;
int weight;
int status;
public Node(int end, int weight, int status) {
this.end = end;
this.weight = weight;
this.status = status;
}
@Override
public String toString() {
return "Node{" +
"end=" + end +
", weight=" + weight +
", status=" + status +
'}';
}
@Override
public int compareTo(Node o){
return Integer.compare(weight,o.weight);
}
}
}
}[느낀점]
4시간정도..?
음 어렵다
이걸 코테에서 마주친다면..음..
풀 수 있도록 연습해야지ㅜㅜ
다익스트라 까먹었었는데 다시 새생각할 수 있었던 좋은 시간이었던것같다.
더 풀어봐야징
'Algorithm' 카테고리의 다른 글
| [PG] 표 편집 - Java (0) | 2022.05.11 |
|---|---|
| [BOJ] 2629 양팔저울 - Java (0) | 2022.05.11 |
| [BOJ] 17825 주사위윷놀이 - Java (0) | 2022.04.28 |
| [BOJ] 17822 원판돌리기 - Java (0) | 2022.04.26 |
| [BOJ] 17837 새로운게임2 - Java (0) | 2022.04.26 |