[2021 카카오 채용연계형 인턴십] 미로 탈출

최민길(Gale)·2023년 4월 11일
1

알고리즘

목록 보기
63/172

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/81304

이 문제는 다익스트라 알고리즘과 비트마스크 기법을 이용하여 풀 수 있습니다.

다익스트라 알고리즘은 최단 경로 탐색 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있습니다. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하여 방문합니다. 이후 방문한 노드를 거쳐 다른 노드로 넘어가는 가중치를 계산해서 최단 거리 테이블을 업데이트하는 방식으로 동작합니다.

비트마스크 기법이란 비트를 활용한 테크닉으로 boolean 배열을 사용하는 대신 이진수의 각 자리의 값을 배열의 인덱스로 보고 각 값이 0이냐 또는 1이냐에 따라 해당 인덱스의 true/false 여부를 확인할 수 있는 기법입니다. 비트 연산자를 이용하기 때문에 O(1)로 빠르게 연산이 수행된다는 장점이 있습니다.

이 문제의 경우 i에서 j까지 이동하는데 소요되는 최소 시간을 graph[i][j]로 설정하여 현재 값과 i에서 j로 이동 시 걸리는 시간과의 최솟값으로 값을 대체합니다. 또한 함정은 최대 10개 있으므로 10자리의 이진수에서 0이면 함정이 켜져 있고 1이면 함정이 꺼져 있는 상태로 설정합니다. 이 때 방문 노드를 확인하는 배열의 경우 check[현재 방의 번호][함정 상태]로 설정하며 함정 상태는 이진수로 변환했을 때 각 자리수 별로 위의 조건대로 설정되어 있는 값을 넣습니다.

방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하여 방문하기 위해 우선순위 큐에 현재 노드에서 이동할 모든 경우의 수를 추가하고 우선순위 큐를 하나씩 poll하면서 현재 노드가 목적지에 도착할 때까지 반복합니다. 이 때 모든 함정을 체크하면서 함정의 상태값을 체크하고 현재 노드가 함정일 경우 이전에 현재 노드가 활성화되어있는지 유무에 따라 함정 활성도를 설정합니다. 이후 이동 가능한 모든 경우의 수에서 함정의 활성도 여부에 따라 graph[start][end]로 이동할 지 graph[end][start]로 이동할 지 결정합니다. 현재 노드와 이동할 노드가 둘 다 함정이거나 둘 다 정상일 경우 상쇄되어 정방향으로 이동하고, 한 쪽만 함정일 경우 역방향으로 이동합니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static final int INF = Integer.MAX_VALUE;
    
    public int solution(int n, int start, int end, int[][] roads, int[] traps) {
        // i에서 j까지 이동하는데 소요되는 최소 시간 = graph[i][j]
        int[][] graph = new int[n+1][n+1];
        
        // 최솟값을 구해야 하므로 최대값으로 graph 초기화
        Arrays.stream(graph).forEach(x -> Arrays.fill(x,INF));
        
        // 자기 자신으로 이동하는 경우는 없으므로 0으로 초기화
        for(int i=1;i<=n;i++)
            graph[i][i] = 0;
        
        // 그래프 조건대로 경로 당 최솟값 추가
        // graph[i][j] 값을 현재 값과 i에서 j로 이동 시 걸리는 시간과의 최솟값으로 추가
        for(int i=0;i<roads.length;i++){
            int s = roads[i][0];
            int e = roads[i][1];
            int t = roads[i][2];
            
            graph[s][e] = Math.min(graph[s][e],t);
        }
        
        // 함정은 최대 10개 있으므로 10자리의 이진수에서 0이면 함정이 켜져 있고 1이면 함정이 꺼져 있는 상태
        // check[현재 방의 번호][함정 상태]
        boolean[][] check = new boolean[n+1][1 << traps.length];
        
        // 우선순위 큐에 시간이 작은 값 순으로 저장
        PriorityQueue<Node> queue = new PriorityQueue<>();
        
        // 시작값 데이터 추가. 처음 위치에서는 이동할 시간값이 없는 상태
        queue.add(new Node(start,0,0));
        
        // 다익스트라 알고리즘 진행
        while(!queue.isEmpty()){
            Node curr = queue.poll();
            
            // end에 도착하면 종료 후 현재까지의 누적 시간값 리턴
            if(curr.number == end) return curr.time;
            
            // 이미 방문한 곳이면 패스
            if(check[curr.number][curr.state]) continue;
            
            // 방문 체크
            check[curr.number][curr.state] = true;
            
            // 현재 노드가 활성화된 함정 여부 체크
            boolean isCurrTrapActivated = false;
            
            // 활성화된 함정들 저장
            HashSet<Integer> activatedTraps = new HashSet<>();
            
            // 모든 함정 하나씩 체크
            for(int i=0;i<traps.length;i++){
                
                // 이진수 자리수로 함정 번호 체크
                int trapNum = 1 << i;
                
                // 현재 함정이 활성화되어있을 경우
                // 현재 노드의 상태값이 1010이고 trapNum이 0010이라면 0010으로 현재 노드의 상태값에서 2번 함정이 활성화되었다는 것을 확인할 수 있다
                if( (curr.state & trapNum) != 0 ){
                    
                    // 현재 함정이 현재 노드와 같을 경우 현재 함정 비활성화
                    // 현재 노드의 상태값이 1010이고 trapNum이 0010일 경우 1010과 1101을 비교하여 1000이 출력, 즉 현재 함정 번호가 비활성화
                    if(curr.number == traps[i]) curr.state &= ~trapNum;
                    
                    // 현재 함정이 현재 노드와 다를 경우 활성화된 함정들 HashSet에 저장
                    else activatedTraps.add(traps[i]);
                }
                
                // 현재 함정이 활성화되어있지 않을 경우
                // 현재 노드의 상태값이 1010이고 trapNum이 0001이라면 0000으로 현재 노드의 상태값에서 1번 함정이 활성화되지 않았다는 것을 확인할 수 있다
                else{
                    // 현재 함정이 현재 노드와 같을 경우 현재 함정 활성화
                    if(curr.number == traps[i]){
                        
                        // 현재 노드의 상태값이 1010이고 trapNum이 0001일 경우 1011이 출력, 즉 현재 함정 번호가 활성화
                        curr.state |= trapNum;
                        
                        // 함정이 활성화되었으므로 활성화된 함정들 HashSet에 저장
                        activatedTraps.add(traps[i]);
                        
                        // 현재 노드가 활성화된 함정 여부를 true로 설정
                        isCurrTrapActivated = true;
                    }
                }
            }
            
            
            // 현재 노드에서 방문할 노드를 확인하여 우선순위 큐에 추가
            for(int i=1;i<=n;i++){
                
                // 같은 위치로는 이동 불가
                if(curr.number == i) continue;
                
                // 다음 이동할 노드가 함정인지 여부 체크
                boolean isNextTrapActivated = activatedTraps.contains(i);
                
                // 현재 노드와 다음 노드 둘 다 함정 또는 둘다 아니라면 상쇄되어 정방향, 즉 graph[start][end]로 움직인다
                if(isCurrTrapActivated == isNextTrapActivated){
                    
                    // 이동 가능한 노드일 경우 큐에 추가
                    if(graph[curr.number][i] != INF)
                        queue.add(new Node(
                            i,
                            curr.time + graph[curr.number][i],
                            curr.state
                        ));
                }
                
                // 둘 중 하나가 함정이라면 역방향, 즉 graph[end][start]로 움직인다
                else{
                    
                    // 이동 가능한 노드일 경우 큐에 추가
                    if(graph[i][curr.number] != INF)
                        queue.add(new Node(
                            i,
                            curr.time + graph[i][curr.number],
                            curr.state
                        ));
                }
            }
        }

        return INF;
    }
}

class Node implements Comparable<Node>{
    int number;
    int time;
    int state;
    
    Node(int number,int time,int state){
        this.number = number;
        this.time = time;
        this.state = state;
    }
    
    @Override
    public int compareTo(Node o){
        // 시간이 작은 순서대로 정렬
        return this.time - o.time;
    }
}

참고 자료 :
https://bellog.tistory.com/196
https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://mygumi.tistory.com/361

profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글