동굴 탐험

문제

프로그래머스 - 동굴 탐험

---

문제 해결 아이디어

위상정렬을 잘 몰랐는데 BFS로 구현 한게 위상정렬이었던 것,
제약조건이 있어서, 특정 방🔒에 들어가기전 방문해야하는 방이 있음 -> pre[] 배열, wait[] 배열을 사용하여 i번 방을 방문하기 전에 방문해야하는 방, i번 방을 방문 한 후에 풀리는 방을 저장

1. 그래프 구성

   • graph 배열에 각 방(0번~n-1번)의 인접한 방 정보를 저장
   • 입력으로 주어진 path를 양방향 간선으로 추가

2. 제약 정보 설정

   • pre 배열은 각 방이 방문되기 전에 반드시 방문해야 하는 선행 방의 번호를 저장하며, 기본값은 -1(제약 없음)
   • order 배열을 순회하며, [A, B] 형태의 제약을 pre[B] = A로 저장
   • wait 배열은 아직 방문하지 못한, 방문해야 할 방을 보류하는 용도로 사용

3. BFS 탐색

   • 0번 방(입구)에서 시작
   • 탐색 중, 인접한 방을 방문할 때 해당 방이 선행 조건을 만족하지 않으면(즉, pre[next]가 방문되지 않았으면) wait에 저장
   • 만약 현재 방문한 방 cur가 선행 조건을 제공하는 방이라면, wait[cur]에 저장된 방을 큐에 추가하여 잠금 해제

4. 최종 확인

   • 모든 방이 방문되었는지 확인하여, 하나라도 방문하지 못했다면 false를 반환하고, 모두 방문했다면 true를 반환

---

코드

import java.util.*;

class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
        // 1. 그래프 구성
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] p : path) {
            graph[p[0]].add(p[1]);
            graph[p[1]].add(p[0]);
        }

        // 2. 제약 정보 설정
        // pre[i] : i번 방을 방문하기 전에 반드시 방문해야 하는 방 (없으면 -1)
        int[] pre = new int[n];
        Arrays.fill(pre, -1);
        // wait[x] : x번 방을 방문한 후에 unlock될, 아직 방문 못한 방 (없으면 -1)
        int[] wait = new int[n];
        Arrays.fill(wait, -1);

        for (int[] o : order) {
            pre[o[1]] = o[0];
        }

        // 0번 방(입구)가 잠겨있으면 탐험 불가능
        if (pre[0] != -1) {
            return false;
        }

        // 3. BFS 탐색 0번 방부터 시작
        boolean[] v = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        v[0] = true;
        q.offer(0);

        while (!q.isEmpty()) {
            int cur = q.poll();

            // cur 방문으로 인해 unlock되어야 하는 방이 있다면 큐에 추가
            if (wait[cur] != -1) {
                int next = wait[cur];
                q.offer(next);
                v[next] = true;
                wait[cur] = -1;
            }

            for (int next : graph[cur]) {
                if (v[next]) {
                    continue;
                }

                // next가 방문 조건(선행 방문)이 있고, 아직 방문 전이라면 next 대기
                if (pre[next] != -1 && !v[pre[next]]) {
                    wait[pre[next]] = next;
                } else {
                    v[next] = true;
                    q.offer(next);
                }
            }
        }

        // 4. 모든 방을 방문했는지 확인
        for (boolean flag : v) {
            if (!flag) {
                return false;
            } 
        }
        return true;
    }
}