[프로그래머스] 동굴 탐험 (JAVA)

목차

1. 문제
2. 문제 조건
3. 문제 조건 분석
4. 알고리즘
5. 코드

문제

https://school.programmers.co.kr/learn/courses/30/lessons/67260

문제 조건

모든 방을 적어도 한 번 방문해야 하고, 제공된 방문선행조건을 만족해야 합니다.

방 개수: 2<=n<=2*10^5

문제 조건 분석

모든 방을 방문하는 것이 조건이기 때문에,
n * k(상수 값)으로 귀결될 수 있다.

알고리즘

특정 방을 방문하기 전에 반드시 먼저 방문할 방이 정해져 있기 때문에 -> 위상정렬 개념을 사용하면 좋다.

동굴의 시작점이 0번 방과 연결되어 있기 때문에 0부터 위상정렬을 이용하여 bfs를 수행하면 찾을 수 있다.

방문하지 못하는 경우는 order을 준수하기 위해 cycle이 생기는 경우임으로, bfs를 사용해서 모든 방을 방문하지 못한다면 false, 방문한다면 true를 사용하면 된다.

추가적으로 Set을 사용하지 않으면 효율성 30번을 통과하지 못하게 된다. 이후 방문할 지점을 Queue에 넣고 수행하는 부분에서 오버헤드가 커서 시간초과가 나는 것으로 보인다.

이 문제에서의 queue는 방문 가능한 것만 기재하는 것으로 알아두면 좋다.

코드

import java.util.*;

class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
        boolean[] visited = new boolean[n];
        List<Integer>[] conns = new List[n];
        int[] orders = new int[n];
        int[] levels = new int[n];

        for(int i=0;i<n;i++){
            conns[i] = new ArrayList<>();
        }

        for (int[] p : path) {
            int start = p[0];
            int end = p[1];

            conns[start].add(end);
            conns[end].add(start);
        }

        for (int[] o : order) {
            int prev = o[0];
            int next = o[1];

            orders[prev] = next;
            levels[next] = 1;
        }

        //0과 연결된 방 방문 설정
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        
        Set<Integer> set = new HashSet<>();

        while (!queue.isEmpty()) {
            int now = queue.poll();
            
            if(levels[now] > 0){
                continue;
            }

            //order 값 있으면 level 감소
            int next = orders[now];
            levels[next]--;
            
            if(!visited[next] && levels[next] == 0 && set.contains(next)){
                queue.add(next);
                visited[next] = true;
            }

            //연결된 값들도 큐에 넣어주기
            for (int end : conns[now]) {
                if (visited[end]) {
                    continue;
                }

                if(levels[end] > 0){
                    set.add(end);
                    continue;
                }
                
                queue.add(end);
                visited[end] = true;
            }
        }


        for (int i = 0; i < n; i++) {
            if(!visited[i]){
                return false;
            }
        }

        return true;
    }
}