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

🖇️ 문제 링크

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

오지 탐험가인 프로도 는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다.

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

 

---

📝 문제 분석

💡

before[y] = x → y를 방문하기 전에 x를 방문 해야 됨 after[x] = y → x를 방문 후에 y를 방문 해야 됨 discovered[y] → y에 갈 수 있는 경로가 있다는 것을 확인은 했음.(방문은 했는지 안했는지 모른다) visited[y] → y에 방문한 적이 있다.

 

1. BFS 탐색을 진행합니다

2. 다음 방을 발견 했을 때, 그 전에 먼저 방문해야 하는 방이 있는지 확인합니다.
   1. 방문 한적이 있을 때 = 큐에 넣는다
   2. 방문 한적이 없을 때 = 지금 들어갈 수 없으므로, discovered 배열에 체크만 합니다

3. 방을 방문했을 때
   1. y방에 방문했을 때, after[y] = x이고, discovered[x]인 경우 x는 y를 방문하지 못해서 못갔었기 때문에 이제는 갈 수 있으므로 x를 큐에 넣습니다.

💡

테스트 케이스 30 : 시작점인 0이 Order 배열에 있는 경우인 것 같습니다. 0번 방 전에 방문 하는 방이 0이 아닌 경우 false를 리턴합니다.

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
        List<Integer>[] adj = new List[n];
        int[] before = new int[n];
        int[] after = new int[n];
        boolean[] visited = new boolean[n];
        boolean[] discovered = new boolean[n];
        
        
        for(int i = 0; i < n; i++)
           	adj[i] = new ArrayList<>();
        
        for(int i = 0; i < n - 1; i++) {
            int u = path[i][0];
            int v = path[i][1];
            adj[u].add(v);
            adj[v].add(u);
        }
        
       	for(int i = 0; i < order.length; i++) {
            before[order[i][1]] = order[i][0];
            after[order[i][0]] = order[i][1];
        } 
        
       	if(before[0] != 0)
            return false;
        
        Queue<Integer> q = new LinkedList<>();
        discovered[0] = true;
        q.add(0);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            visited[cur] = true;
            if(after[cur] != 0 && discovered[after[cur]]) {
                q.add(after[cur]);
            }
            
            for(var next : adj[cur]) {
                if(visited[next]) continue;
                if(before[next] != 0 && !visited[before[next]]) {
                    discovered[next] = true;
                    continue;
                }
                
               	discovered[next] = true; 
                q.add(next);
            }
        }
        
        for(var b : visited) 
            if(!b) return false;

        return true;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0