[BOJ 4803] 트리 (Java, DFS)

 

---

문제 링크 

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

4803번: 트리

---

재귀 함수로 그래프 사이클 판별하는 함수가 이해 되지 않아 몇일 소요
- 재귀 함수를 스택으로 생각 
- 이미 방문한 적 있고, 부모 노드가 다른 경우 사이클 발생 (=그래프)

 

풀이 

- 케이스별로 정점 N, 간선 M 이 주어질 때 트리의 개수를 구하여 형식에 맞게 출력하게 됨 

- 이때 연결된 간선이 없는 정점 또한 트리 개수로 카운팅함

- 재귀 함수 기법을 활용하여 그래프 판별 수행함 (*visit 배열과 부모노드 번호 활용)

- 이에 따라 시간복잡도 : O(N) 만큼 소요됨

 

케이스 3번의 경우 

6 6  -- 정점 N, 간선 M
1 2
2 3
1 3
4 5
5 6
6 4

1	2, 3
2	1, 3
3	1, 2
4	5, 6
5	4, 6
6	4, 5

 

1번 노드 부터 조회 (부모 노드 0으로 할당)

i) 1번 방문 처리

1	2	3	4	5	6
T	F	F	F	F	F

ii) 연결 간선 확인

- 둘다 방문한적 없기 때문에 isCylce(2, 1) , isCylce(3,1) 실행

 

isCycle(2, 1) 실행      // (3,1)은 생략

i) 2번 방문 처리

1	2	3	4	5	6
T	T	F	F	F	F

ii) 연결 간선 확인

- 1번 노드는 방문한적 있고, 부모 노드라서 return false

- 3번 노드는 방문한적 없기 때문에 isCylce(3,2) 실행

 

isCycle(3, 2) 실행

i) 3번 방문 처리

1	2	3	4	5	6
T	T	T	F	F	F

ii) 연결 간선 확인

- 2번 노드는 방문한적 있고, 부모노드라 return false

- 1번 노드는 방문한적있고, 부모 노드가 아니기 때문에 그래프 발생 확인 (return true)

 

 

참고. 기술 블로그 중에 트리 성질을 이용해서 풀이한 방식도 있었음 

* 양방향 간선이라 할 때
총 간선의 개수 = (정점 - 1) * 2

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
     static StringBuilder sb = new StringBuilder();

    static int N, M, CASE_NUMBER;

    static List<Integer>[] adj;

    static boolean[] visit;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        CASE_NUMBER = 1;
        String str = "";
        while(!(str = br.readLine()).equals("0 0")) {
            st = new StringTokenizer(str);

            N = Integer.parseInt(st.nextToken()); // 정점 개수
            M = Integer.parseInt(st.nextToken()); // 간선 개수

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

            for(int i = 1; i <= M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                adj[from].add(to);
                adj[to].add(from);
            }

            for(int i = 1; i <= N; i++) {
                Collections.sort(adj[i]);
            }

            visit = new boolean[N + 1];
            pro();

            CASE_NUMBER += 1;
        }
    }

    static void addResult(int caseNumber, int treeCount) {
        if(treeCount > 1) {
            sb.append(String.format("Case %d: A forest of %d trees.", caseNumber, treeCount)).append("\n");
        } else if(treeCount == 1) {
            sb.append(String.format("Case %d: There is one tree.", caseNumber)).append("\n");
        } else {
            sb.append(String.format("Case %d: No trees.", caseNumber)).append("\n");
        }
    }

    static boolean isCycle(int x, int prev) {
        visit[x] = true;
        for(int y : adj[x]) {
            if(!visit[y]) {
                if(isCycle(y, x)) return true;
            } else if(y != prev) {
                return true;
            }
        }

        return false;
    }

    static void pro() {
        int treeCount = 0;
        for(int i = 1; i <= N; i++) {
            if(!visit[i] && !isCycle(i, 0)) treeCount += 1;
        }

        addResult(CASE_NUMBER, treeCount);
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
    
}