[틀림] [자바] 프로그래머스 동굴탐험 // 순서가있는 dfs, 사이클검사, 위상정렬

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

프로그래머스

자바에서 adj 만드는법

static ArrayList<Integer> adj[] = new ArrayList [200004];

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

for(int i=0;i<path.length;++i){
    adj[path[i][0]].add(path[i][1]);
    adj[path[i][1]].add(path[i][0]);
}

//디버깅
for(int i=0;i<200004;++i){
    if(adj[i].size()>0){
        System.out.println(adj[i]);
    }
}

dfs

억까, 마지막 tc에서 n이 너무커서 스택 오버플로우 나는것으로 추정

그리고, prevVisit, nextVisit같은 상태가 많아져서 복잡해짐. 

실전에서 발상을 떠올리고 구현가능한가? 부정적.

파이썬은 또 통과하네??

import java.util.*;

public class Solution {
    // 전체 방 개수
    private int N;
    // 그래프 인접 리스트: graph[v] = v에 인접한 방 리스트
    private List<Integer>[] graph;
    // prevVisit[b] = a 이면, b를 방문하려면 먼저 a를 방문해야 함
    private int[] prevVisit;
    // nextVisit[a] = b 이면, a를 방문한 뒤에 b를 바로 탐색할 대상
    private int[] nextVisit;
    // check[v] = true 이면 v를 이미 방문했거나 잠금 대기 중 표시
    private boolean[] check;

    public boolean solution(int n, int[][] path, int[][] order) {
        // 1) 전역 변수 초기화
        N = n;
        graph = new ArrayList[N];
        prevVisit  = new int[N];
        nextVisit  = new int[N];
        check      = new boolean[N];

        // 2) 그래프: 모든 방에 대해 빈 리스트 생성
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 3) path 배열을 순회하며 양방향 간선 추가
        for (int[] p : path) {
            int a = p[0], b = p[1];
            graph[a].add(b);
            graph[b].add(a);
        }

        // 4) order 배열을 순회하며 선행(prevVisit) 정보 설정
        for (int[] o : order) {
            int a = o[0], b = o[1];
            prevVisit[b] = a;
        }

        // 5) 0 번 방에 선행 조건이 있으면 시작할 수 없음
        if (prevVisit[0] != 0) {
            return false;
        }

        // 6) 시작 방(0번) 방문 표시
        check[0] = true;
        //    0번 방에 연결된 방들에 대해 DFS 탐색 시작
        for (int nxt : graph[0]) {
            dfs(nxt);
        }

        // 7) 최종 방문된 방 개수 세기
        int cnt = 0;
        for (boolean visited : check) {
            if (visited) cnt++;
        }

        // 8) 모두 방문했으면 true, 아니면 false
        return cnt == N;
    }

    // 깊이 우선 탐색(재귀)
    private void dfs(int v) {
        // 1) 이미 방문했거나 대기 중인 방이면 종료
        if (check[v]) {
            return;
        }

        // 2) 이 방을 방문하기 위해 선행 방(prevVisit[v])이 아직 방문되지 않았다면
        //    선행 방에서 대기 중인 후행(nextVisit)으로 등록하고 대기
        int pre = prevVisit[v];
        if (pre != 0 && !check[pre]) {
            nextVisit[pre] = v;
            return;
        }

        // 3) 방문 처리
        check[v] = true;

        // 4) 이 방을 방문함으로써 즉시 탐색 가능해지는 후행 방이 있으면 재귀 호출
        int nxtOrder = nextVisit[v];
        if (nxtOrder != 0) {
            dfs(nxtOrder);
        }

        // 5) 일반 인접 방들에 대해 재귀 호출
        for (int u : graph[v]) {
            dfs(u);
        }
    }
}

bfs

같은로직, 통과함

dfs는 스택이 터져서 통과못함.

import java.util.*;

public class Solution {
    // 전체 방 개수
    private int N;
    // 그래프 인접 리스트: graph[v] = v에 인접한 방 리스트
    private List<Integer>[] graph;
    // prevVisit[b] = a 이면, b를 방문하려면 먼저 a를 방문해야 함
    private int[] prevVisit;
    // nextVisit[a] = b 이면, a를 방문한 뒤에 b를 바로 탐색할 대상
    private int[] nextVisit;
    // check[v] = true 이면 v를 이미 방문했거나 잠금 대기 중 표시
    private boolean[] check;

    public boolean solution(int n, int[][] path, int[][] order) {
        // 1) 전역 변수 초기화
        N = n;
        graph     = new ArrayList[N];
        prevVisit = new int[N];
        nextVisit = new int[N];
        check     = new boolean[N];

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

        // 2) path 배열로 양방향 간선 구성
        for (int[] p : path) {
            graph[p[0]].add(p[1]);
            graph[p[1]].add(p[0]);
        }

        // 3) order 배열로 선행(prevVisit) 정보 설정
        for (int[] o : order) {
            prevVisit[o[1]] = o[0];
        }
        // 0번 방에 선행 조건이 있으면 불가
        if (prevVisit[0] != 0) {
            return false;
        }

        // 4) BFS 초기화
        Queue<Integer> queue = new LinkedList<>();
        // 0번 방부터 시작
        check[0] = true;
        queue.offer(0);

        // 5) BFS 루프
        while (!queue.isEmpty()) {
            int cur = queue.poll();

            // (A) 순서 제약 해제: cur 방문 후 nextVisit[cur]이 있으면 큐에 추가
            int nxtOrder = nextVisit[cur];
            if (nxtOrder != 0 && !check[nxtOrder]) {
                check[nxtOrder] = true;
                queue.offer(nxtOrder);
            }

            // (B) 일반 인접 방 탐색
            for (int nxt : graph[cur]) {
                if (check[nxt]) continue;

                // 선행 미충족인 경우 스킵하고, nextVisit으로 대기 등록
                if (prevVisit[nxt] != 0 && !check[prevVisit[nxt]]) {
                    nextVisit[prevVisit[nxt]] = nxt;
                } else {
                    check[nxt] = true;
                    queue.offer(nxt);
                }
            }
        }

        // 6) 방문된 방 수 확인
        int visitedCount = 0;
        for (boolean v : check) {
            if (v) visitedCount++;
        }
        return visitedCount == N;
    }
}

 

 

위상정렬

문제 자체에 "순서"라는 키워드가 있으므로, 위상정렬을 떠올릴 수 있다.

단뱡향그래프로 만들고, 사이클이 없으면 true를 리턴하면 된다.

path 입력대로 단방향을 바로 만들면 안되나요?

bfs로 양뱡향을 단방향으로 만들기

초기에는 양방향으로 만든후, bfs를 돌면서 adj에 넣어주면 된다.

indegree 갱신은 덤

boolean[] seen = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        seen[0] = true;
        q.offer(0);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : undirected[u]) {
                if(seen[v]) continue;
                seen[v] = true;
                adj[u].add(v);    // u → v 방향 간선 추가
                inDegree[v]++;    // v 진입차수 증가
                q.offer(v);
            }
        }

위상정렬 & 사이클체크

위상정렬을 indegree가 0인것을 큐에넣고

인접(nxt) 들의 indegree를 -1 빼고, 0이면 큐에넣는다. 반복

vis이 필요없는게 특징.

그리고 사이클이 있는경우는 차수가 0이 안됨 -> 해당 노드는 큐에안들어가서 방문이 안된다.

이걸 이용해서 cnt가 노드 갯수랑 다르면 사이클이 있는것이다.

위상정렬 전체코드

import java.util.*;

public class Solution {
    public boolean solution(int n, int[][] path, int[][] order) {
        // 1) 트리만 방향화할 인접리스트와 진입차수 초기화
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        int[] inDegree = new int[n];

        // 2) 양방향 경로를 한 방향 트리로 변환 (BFS)
        List<Integer>[] undirected = new ArrayList[n];
        for (int i = 0; i < n; i++) undirected[i] = new ArrayList<>();
        for (int[] p : path) {
            undirected[p[0]].add(p[1]);
            undirected[p[1]].add(p[0]);
        }
        boolean[] seen = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        seen[0] = true;
        q.offer(0);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : undirected[u]) {
                if(seen[v]) continue;
                seen[v] = true;
                adj[u].add(v);    // u → v 방향 간선 추가
                inDegree[v]++;    // v 진입차수 증가
                q.offer(v);
            }
        }

        // 3) 순서 제약을 가상 간선으로 추가
        for (int[] o : order) {
            int a = o[0], b = o[1];
            // 0번 방이 제약 대상이면 즉시 실패
            if (b == 0) return false;
            adj[a].add(b);
            inDegree[b]++;
        }

        int cnt=0; //방문한 노드수 
        // 4) 위상정렬 (Kahn’s Algorithm)
        Queue<Integer> q2 = new LinkedList<>();
        // 차수0인거 넣기
        for(int i=0;i<n;++i){
            if(inDegree[i]==0) q2.offer(i);
        }
        while(q2.size()>0){
            int cur = q2.poll();
            cnt++;
            for(int nxt : adj[cur]){
                inDegree[nxt]--;
                if(inDegree[nxt]==0){
                    q2.offer(nxt);
                }
            }
        }
        

        // 5) 방문 개수 검증
        return cnt == n;
    }
}

질문) 사이클검사에 dfs를 쓰면 안되나요?

위상정렬시 cnt==n 조건은 두가지 의미를 가짐

dfs는 사이클이없는지만 확인, 0번에서 도달가능한지 또 확인해줘야하고, 코드가 점점 복잡해짐.

위상정렬 승.

정리

순서가 있는 그래프 문제는 사이클 검사로 환원해서 풀자.

사이클 검사에 위상정렬을 이용하는게 dfs보다 코드가 간결하고 쉽다.

 

 

 

레퍼런스

https://haeseok.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%8F%99%EA%B5%B4-%ED%83%90%ED%97%98-a669d62f304d

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

https://www.youtube.com/watch?v=Th-gLZUrd04