[백준] 4803번 : 트리

4803번: 트리

---

[DFS]

다수의 테스트 케이스 중 DFS를 이용해 사이클이 존재하는 것을 찾아 제외하고, 트리의 개수를 찾는 문제이다. 트리의 특징은 문제에서 잘 나타내어주고 있으며, 정점이 하나만 있는 것 역시 트리라고 본다. 문제의 입력과 출력이 번거로워서 그렇지 문제 자체의 난이도는 크게 어렵지 않다고 생각된다.

 

사이클을 찾는 방법은 글로 푸는 것 보다 코드가 간단하므로 코드를 보는 것이 더 빠르게 이해가 될 것 같다.

    static boolean DFS(int x, int before){
        if(visit[x])
            return false;

        boolean result = true;
        visit[x] = true;

        for(int next:list[x])
            if(next != before)
                result &= DFS(next, x);

        return result;
    }

위 코드는 DFS 메서드인데, boolean 타입을 반환한다. 반환 값이 true이면 트리라는 뜻이고, false면 사이클이 존재하므로 그래프가 된다.

 

# Code </>

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

public class Main {

    static List<Integer>[] list;
    static boolean[] visit;

    static boolean DFS(int x, int before){
        if(visit[x])
            return false;

        boolean result = true;
        visit[x] = true;

        for(int next:list[x])
            if(next != before)
                result &= DFS(next, x);

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = 1;

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            if(n == 0 && m == 0) break;

            list = new ArrayList[n+1];
            visit = new boolean[n+1];

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

            for(int i=0; i<m; i++){
                st = new StringTokenizer(br.readLine());

                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                list[v1].add(v2);
                list[v2].add(v1);
            }

            int cnt = 0;
            for(int i=1; i<=n; i++)
                if(!visit[i] && DFS(i, 0))
                    cnt++;

            sb.append(String.format("Case %d: ", t++));

            if(cnt == 0)      sb.append("No trees.");
            else if(cnt == 1) sb.append("There is one tree.");
            else              sb.append(String.format("A forest of %d trees.", cnt));

            sb.append('\n');
        }
        System.out.print(sb);
    }
}