[프로그래머스] 2020 카카오 인턴십 - 동굴 탐험 - 자바(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/67260?language=java 

코딩테스트 연습 - 동굴 탐험

 

문제 해석

n개의 방으로 이루어진 지하 동굴을 탐험하고자 한다.

모든 방에는 0부터 n-1번까지 번호가 붙어있습니다.

출발을 무조건 0번 방부터 시작합니다. (시작점은 0)

각 방들은 양방향으로 연결되어있습니다. (양방향 그래프)

서로 다른 두 방을 연결하는 통로는 오직 하나입니다. (중복 간선 없음)

임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지

임의의 두 방 사이에 이동이 불가능한 경우는 존재하지 않음

 

탐험 계획
- 모든 방을 적어도 한 번은 방문하고자 함 (최소 신장 트리)?

- 특정 방을 방문하기 전에 먼저 방문할 방이 정해져 있음(순서가 존재) - 비트 마스킹?

- 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 1개

- 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다. (각각 서로 의존하는 방이 다름)

- 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.

 

예를 들어

A -> B (A를 먼저 방문하고 B를 방문하는) 형태로 유일합니다.

 

다음과 같은 방문순서는 잡히지 않습니다.

A -> B, A -> C         A를 방문 후에 방문해야 할 방이 B와 C로 2개 이상이 인 경우는 없습니다.

X -> A, Z -> A         A를 방문하기 전에 방문해야 할 방이 X와 Z로 2개 이상인 경우는 없습니다.

A -> B -> C             B처럼 A방문 후이면서 동시에 C방문 전인 경우는 경우는 없습니다.

 

제약 조건

n은 2 이상 200,000 이하입니다.

path 배열의 세로행 길이는 n-1입니다.

path 배열의 원소는 [방 번호 A, 방 번호 B]  형태입니다.

두방 A, B사이를 연결하는 통로를 나타냅니다. ( 순서는 상관없습니다 - 어차피 양방향)

 

order 배열의 길이는 1 이상 (n/2) 이하입니다.

order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.

A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.

 

규칙에 맞게 모든 방을 탐 헌 할 수 있다면 true를 return 합니다

 

 

문제 풀이 전 설계

직관적으로 떠오르는 방법은 비트 마스킹을 활용한 전체 탐색입니다 하지만 조금 걱정되는 부분은 n = 200,000이라는 큰 수가 걱정됩니다.

 

문제 중에서 모든 방을 적어도 한 번은 방문하고자 한다는 조건이 존재하기 때문에 최소 신장 트리 쪽으로 접근을 해보고자 합니다.

 

또한 아래의 조건들이 무엇을 뜻하는가를 유심히 생각해봤는데 바로 HashSet을 사용해라는 말을 느껴집니다.

 

1. 갈 수 있는 노드들을 모두 탐색해봅니다. ( 이때 order는 [A, B] A방을 먼저 방문한 후 B번방을 방문해야 함을 나타냅니다.)

 

2. 이를 기반으로 구조를 바꾼 HashMap <Integer, Integer> dependencies를 만들어 B가 key이고 A가 방문해야 하는 값으로 변환합니다.

 

3. 탐색하는 노드가 HashMap dependencies에 key로 존재하면 Set <Integer> visited를 만들어 여기서는 의존하는 방문 값이 visited에 존재하는지 확인합니다.

 

4. 만약 visited에 존재하지 않는다면 이동할 수 없습니다. (이동 불가능한 노드들은 따로 관리해 줍니다.)

 

5. 탐색이 가능한 노드들은 모드 탐색하고 이동 불가능한 노드들을 다시 탐색해 봅니다.

 

6. 이동 불가능한 노드들을 다시 탐색했을 때 이동 가능한 경우가 존재하지 않는다면 false를 반환합니다.

 

이때 만약 0이 의존하고 있는 값이 있으면 시작부터 false를 반환해줘야 합니다! Edge case 조심하세요

 

초기 코드 : 효율성 테스트 10 : 실패(시간 초과) : 97.7점

import java.util.*;

class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
        boolean answer = true;

        HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();
        //양방향 인접리스트 생성한다
        for(int[] e : path){
            if(!tree.containsKey(e[0])){
                tree.put(e[0], new ArrayList<>());
            }
            if(!tree.containsKey(e[1])){
                tree.put(e[1], new ArrayList<>());
            }            
            tree.get(e[0]).add(e[1]);
            tree.get(e[1]).add(e[0]);
        }

        //order= [A,B] A를 방문하기 전에는 B를 방문해야 한다는 의미
        HashMap<Integer, Integer> dependencies = new HashMap<>();
        for(int[] e: order){
            //A의 의존성을 확인하기 위한 HashMap
            dependencies.put(e[1],e[0]);
        }

        if(dependencies.containsKey(0)){                        
            return false;
        }
        
        //방문체크 Set
        HashSet<Integer> visited = new HashSet<>();

        //0부터 시작
        Queue<Integer> canMove = new LinkedList<>();
        Set<Integer> waiting = new HashSet<>();
        canMove.add(0);
        
     
            
        while(true) {
            while (!canMove.isEmpty()) {
                int curNode = canMove.poll();
                visited.add(curNode);
                                
                //다음으로 갈 수 있는 노드들
                ArrayList<Integer> nextNodes = tree.get(curNode);
                for (Integer next : nextNodes) {
                    //방문 이미 했으면 가지마
                    if(visited.contains(next)){
                        continue;
                    }
                    //의존성을 가지고 있지 않으면
                    if (!dependencies.containsKey(next)) {
                        canMove.add(next);
                        continue;
                    }
                    //의존성을 가지고 있으면
                    //의존하는 노드가 방문 되었는지 확인
                    if (visited.contains(dependencies.get(next))) {
                        canMove.add(next);
                    //의존하는 노드가 현재 방문하지 않았다면 대기
                    } else {                     
                        waiting.add(next);
                    }                                   
                }
            }

            //만약 모든노드들이 방문되었다면 break;
            if(visited.size() == n){
                break;
            }

            //현재 갈 수 있는 노드들을 모두 갔으면 waiting이 움직일 수 있는지 확인
            int curWaitingSize = waiting.size();
            ArrayList<Integer> removeList = new ArrayList<>();
            for(Integer wait : waiting){
                //wait들은 모두 의존성을 가지고 있는 사람들임
                //만약 wait가 의존하고 있는 노드가 방문되었다면?
                if(visited.contains(dependencies.get(wait))){
                    canMove.add(wait);
                    removeList.add(wait);
                }
            }
            //움직일 수 있는건 제거
            for(Integer removeValue : removeList){
                waiting.remove(removeValue);
            }

            //만약 못움직인다면? false return
            if(waiting.size() == curWaitingSize){
                answer = false;
                break;
            }
        }


        return answer;
    }
}

해당 풀이에서 기다리는 친구들은 계속 기다려야 할 텐데 Queue에 추가하면 그만큼 시간 복잡도가 복잡해질 것이라고 생각했습니다.

 

따라서 만약에 A를 방문하기 위해서 B를 방문해야 하는 노드가 있다면 HashMap <B, A>로 구성하여 만약 B가 방문되면 Queue에 A를 넣어주도록 하였습니다.

 

그러자 시간 초과가 해결되었습니다!

 

정답 코드 : 100점

import java.util.*;

class Solution {
    public static boolean solution(int n, int[][] path, int[][] order) {
        boolean answer = true;
        HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();
        //양방향 인접리스트 생성한다
        for (int[] e : path) {
            if (!tree.containsKey(e[0])) {
                tree.put(e[0], new ArrayList<>());
            }
            if (!tree.containsKey(e[1])) {
                tree.put(e[1], new ArrayList<>());
            }
            tree.get(e[0]).add(e[1]);
            tree.get(e[1]).add(e[0]);
        }

        //order= [A,B] A를 방문하기 전에는 B를 방문해야 한다는 의미
        HashMap<Integer, Integer> dependencies = new HashMap<>();

        for (int[] e : order) {
            //A의 의존성을 확인하기 위한 HashMap
            dependencies.put(e[1], e[0]);
        }

        if (dependencies.containsKey(0)) {            
            return false;
        }

        Queue<Integer> canMove = new LinkedList<>();
        HashMap<Integer, Integer> waiting = new HashMap<>(); // 대기체크 Set
        HashSet<Integer> visited = new HashSet<>(); //방문체크 Set
        canMove.add(0); //0부터 시작
        visited.add(0);
        while (!canMove.isEmpty()) {
            int curNode = canMove.poll();
            //만약 현재노드가 의존
            if(waiting.containsKey(curNode)){
                int nextNode = waiting.get(curNode);
                visited.add(nextNode);
                canMove.add(nextNode);
            }

            //다음으로 갈 수 있는 노드들
            ArrayList<Integer> nextNodes = tree.get(curNode);
            for (Integer next : nextNodes) {
                //방문 이미 했으면 가지마
                if (visited.contains(next)) {
                    continue;
                }
                //의존성을 가지고 있지 않으면
                if (!dependencies.containsKey(next)) {
                    canMove.add(next);
                    visited.add(next);
                    continue;
                }
                //의존성을 가지고 있으면
                //의존하는 노드가 방문 되었는지 확인
                if (visited.contains(dependencies.get(next))) {
                    canMove.add(next);
                    visited.add(next);
                    //의존하는 노드가 현재 방문하지 않았다면 대기
                } else {
                    waiting.put(dependencies.get(next),next);
                }
            }
        }

        if(visited.size() != n){
            answer = false;
        }
        return answer;
}
}