[백준] 4803 : 트리

https://www.acmicpc.net/problem/4803

 

[풀이과정]

DFS 문제였다. 탐색을 하며 사이클이 존재하는지 여부를 체크하는 것이 중요.

처음엔 이미 방문한 노드를 재방문했을 때 사이클이 발생한다고 했는데 여기서 오류가 생겼다.

이미 방문한 노드 중엔 현재 주변을 탐색 중인 노드가 포함이었는데 이때는 제외했어야 했다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int N = -1, M = -1, tc;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static boolean isCycle;

    public static void main(String[] args) throws IOException {
        while (true) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            //입력 종료 조건
            if (N == 0 && M == 0) {
                break;
            }

            init();

            //트리 개수
            int treeCount = 0;

            for (int i = 1; i <= N; i++) {
                //아직 방문 전인 노드이면
                if (!visited[i]) {
                    //사이클이 없는 상태로 탐색 시작
                    isCycle = false;
                    if (dfs(i, 0)) { // 트리 여부 확인
                        treeCount++; // 트리이면 트리 개수 증가
                    }
                }
            }

            //테스트 케이스 번호 증가
            tc++;
            if (treeCount == 0) {
                sb.append("Case ").append(tc).append(": No trees.\n");
            } else if (treeCount == 1) {
                sb.append("Case ").append(tc).append(": There is one tree.\n");
            } else {
                sb.append("Case ").append(tc).append(": A forest of ").append(treeCount).append(" trees.\n");
            }
        }

        System.out.print(sb);
    }

    static void init() throws IOException {
        graph = new ArrayList[N + 1];
        visited = new boolean[N + 1];

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            //양방향
            graph[a].add(b);
            graph[b].add(a);
        }
    }

    // DFS로 사이클 존재 여부 확인 (재귀 방식)
    static boolean dfs(int node, int parent) {
        visited[node] = true;

        for (int next : graph[node]) {
            //아직 방문 전인 노드이고
            if (!visited[next]) {
                //사이클이 존재하면 끝내기
                if (!dfs(next, node)) {
                    return false;
                }
            }
            //방문한 노드가 부모 노드가 아니면 사이클
            else if (next != parent) {
                isCycle = true;
            }
        }
        return !isCycle; // 사이클이 있으면 false, 없으면 true
    }
}