알고리즘
프로그래머스 미로 탈출 (JAVA)
박카스마시며코딩
2022. 4. 21. 18:55
https://programmers.co.kr/learn/courses/30/lessons/81304
코딩테스트 연습 - 미로 탈출
4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4
programmers.co.kr
2021 카카오 인턴십 for Tech developers 코딩 테스트 해설
2021년 카카오의 여름 인턴십의 첫 번째 관문인 코딩 테스트가 지난 2021년 5월 8일에 4시간에 걸쳐 진행되었습니다. 이번 인턴 코딩 테스트에서는 5문제가 출제되었습니다. 이전과 동일하게 쉬운
tech.kakao.com
위의 해설을 참조하면서 문제를 해결하였습니다.
저는 다익스트라와 비트 마스킹을 통해 문제를 해결하였습니다.
저는 배열로 경로를 표시하였습니다.
(n^2에 비해 road가 현저히 적기 때문에 처음에 인접 리스트로 표현하려 하였지만, 구현부분에서 너무 힘들어서 배열로 표현하였습니다.)
저는 비트 마스크를 통해 지금 어떤 trap을 밟았는지를 확인하였습니다. 비트 마스킹은 밟은 트랩을 다시 밟으면 안 밟은 것 처럼 해야하기 때문에 ^(XOR)을 통해 표시하였습니다.
방문 체크는 Node의 toCheckVisited메서드를 통해 현재 위치와 현재 밟은 trap을 String으로 리턴하여 이와 같은 값이 있으면 진행하지 않도록 하였습니다.
import java.util.*;
class Solution {
static class Node{
int now;
int trap;
int weight;
public Node(int now,int trap,int weight){
this.now = now;
this.trap = trap;
this.weight = weight;
}
@Override
public String toString(){
return now+","+trap+","+weight;
}
public String toCheckVisited(){
return now+","+trap;
}
}
public static int solution(int n, int start, int end, int[][] roads, int[] traps) {
int answer = 0;
int[][] map = new int[n+1][n+1];
Map<Integer,Integer>isTrap = new HashMap<>();
init(map,isTrap,traps,roads);
answer = dij(map,isTrap,traps,start,end,n);
return answer;
}
private static final int INF = 987654321;
private static int dij(int[][] map,Map<Integer,Integer>isTrap,int[] traps,int start,int end,int n){
Map<String,Integer> visited = new HashMap<>();
// boolean[][] visited = new boolean[n+1][1>>n];
PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2)->{
return o1.weight - o2.weight;
});
Node startNode = new Node(start,0,0);
pq.offer(startNode);
visited.put(startNode.toCheckVisited(),0);
while(!pq.isEmpty()){
Node node = pq.poll();
System.out.println(node);
if(node.now == end){
return node.weight;
}
int now = node.now;
int weight = node.weight;
boolean[] nowTrap = trapNumber(traps,node.trap,n);
for(int i = 1 ; i <= n ; i++){
if(i == now){
continue;
}
int tempTrap = node.trap;
int temp = checkIsTrap(isTrap,i);
int tempWeight = weight;
if(temp != -1){
tempTrap = tempTrap ^ (1 << temp);
}
if(map[now][i] > 0 && ((!nowTrap[now] && !nowTrap[i])
|| (nowTrap[now] && nowTrap[i]))){
tempWeight += map[now][i];
}else if( (nowTrap[now] || nowTrap[i]) && map[i][now] > 0 ){
tempWeight += map[i][now];
}
if(tempWeight == weight){
continue;
}
Node next = new Node(i,tempTrap,tempWeight);
if(visited.getOrDefault(next.toCheckVisited(),INF) > tempWeight){
visited.put(next.toCheckVisited(),tempWeight);
pq.offer(next);
}
}
}
return -1;
}
private static void init(int[][] map, Map<Integer,Integer> isTrap,int[] traps ,int[][] roads){
for(int[] road : roads){
int a = road[0];
int b = road[1];
int weight = road[2];
if(map[a][b] == 0){
map[a][b] = weight;
}else{
map[a][b] = Math.min(map[a][b],weight);
}
}
int index = 0;
for(int trap : traps){
isTrap.put(trap,index++);
}
}
private static int checkIsTrap(Map<Integer,Integer>isTrap,int num){
return isTrap.getOrDefault(num,-1);
}
private static boolean[] trapNumber(int[] traps,int num,int n){
boolean[] booleanIsTrap = new boolean[n+1];
if(num == 0){
return booleanIsTrap;
}
for(int i = 0 ; i < 10 ; i++){
if( (num & 1<<i) > 0){
int temp = traps[i];
booleanIsTrap[temp] = true;
}
}
return booleanIsTrap;
}
}