백준 9466 텀 프로젝트 - DFS

DFS가 사용되는 상황은 크게 3가지이다.
1. 한 정점과 연결된 모든 정점을 찾는 문제
2. 경로를 찾아야 하는 문제
3. 사이클 존재 유무를 찾아야 하는 문제

9466번 텀 프로젝트는 3번 유형에 해당한다.

사이클의 존재유무는 기본적으로 방문했던 노드를 다신 방문할 경우 해당 노드는 사이클에 속한 노드이다.

DFS는 기본적으로 visited 변수를 둠으로써 방문했던 노드의 재방문을 허락하지 않는다.

사이클을 탐지하기 위해 방문했던 노드의 재방문을 허락하고 사이클 내부에서 무한루프가 생성되는걸 방지하기 위해 cycle 1차원 배열이 추가로 필요하게 된다.

cycle은 각 노드가 사이클인지, 아닌지, 아직 모르는지 를 담고있는 1차원 배열이다.

코드를 구성해나가는 과정

몸통

기본적으로 연결된 노드를 추가로 방문하므로 해당 코드블럭이 필요하다.

        for (int next : adj.get(cur)){
            dfs(next);
        }

머리

함수 시작부분에 방문했던 노드인지 확인하는 로직이 필요하다. 만약 방문했던 노드의 경우 cycle이라는 정보를 저장해준다.

 private static void dfs(int cur) {
        if (visited[cur]){
            // 해당 노드는 사이클
            cycle[cur]=1; // 0이면 모름, 1이면 사이클, 2면 사이클아님
        }

        visited[cur]=true;

꼬리

DFS를 진행했음에도 cycle이라고 확정받지 못한 경우 사이클이 아니라고 확정할 수 있다.

        if (cycle[cur]==0){
            cycle[cur]=2;
        }

        visited[cur]=false;

최종코드 (머리+몸통+꼬리)

이제 cycle이 아닌 노드만 순차적으로 DFS를 통해 탐색해주면 된다.

// 메인함수 내부
            for (int i = 1; i <= n; i++) {
                // 1번 학생부터 탐색
                if (cycle[i]==0) {
                    dfs(i);
                }
            }
           
// DFS 로직
 private static void dfs(int cur) {
        if (visited[cur]){
            // 해당 노드는 사이클
            cycle[cur]=1; // 0이면 모름, 1이면 사이클, 2면 사이클아님
        }

        visited[cur]=true;

        for (int next : adj.get(cur)){
            if (cycle[next]==0) {
                dfs(next);
            }
        }

        if (cycle[cur]==0){
            cycle[cur]=2;
        }

        visited[cur]=false;
    }