BOJ 4803 트리 (Java)

문제 탐색하기

DFS로 Tree여부를 판정하는 문제이다.

트리의 정의에 따라, 하나의 연결 요소가 트리인지 확인하려면 두 가지 조건을 만족해야 한다.

1. 정점 개수 (v)와 간선 개수 (e)가 트리의 특징을 만족해야 한다.
   • 트리는 e = v−1 을 만족해야 한다.
   • 그러나 문제에서 주어진 그래프는 양방향 그래프이므로, DFS 탐색 시 하나의 간선을 두 번 세게 된다.
     • 따라서 트리 조건을 확인할 때는 e = 2 × (v−1) 을 만족하는지 검사한다.
2. 사이클이 없어야 하며, 하나의 연결 요소여야 함
   • DFS 탐색을 통해 방문한 노드와 간선 개수를 세면서, 연결 요소 단위로 검증한다.
   • 방문한 모든 정점이 하나의 연결 요소로 연결되어 있고, 간선 수 조건을 만족하면 트리로 판정한다.

6 3
1 2
2 3
3 4

다음 예제에서 트리의 개수는 3개이다.

1. 1 – 2 – 3 – 4
2. 5
3. 6

코드 설계하기

구현 방법

• 입력 처리
  • 여러 개의 테스트 케이스를 처리해야 하므로, BufferedReader를 사용해 입력을 받는다.
  • 각 테스트 케이스의 첫 줄에서 N(정점 개수)와 M(간선 개수)을 입력받는다.
  • 이후 M개의 간선 정보를 인접 리스트 그래프에 저장한다.
  • 0 0이 입력되면 프로그램을 종료한다.
• 그래프 탐색 (DFS)
  • 방문하지 않은 모든 노드를 대상으로 DFS를 실행한다.
  • DFS 실행 시 해당 연결 요소의 정점 개수(vCnt)와 간선 개수(eCnt)를 센다.
  • DFS 탐색이 끝나면, eCnt == 2 * (vCnt - 1) 조건을 만족하는지 확인하여 트리 여부를 판단한다.
• 출력 형식 맞추기
  • switch 문을 활용한다.
    • 트리 개수가 0개이면 "No trees.",
    • 1개이면 "There is one tree.",
    • 여러 개이면 "A forest of X trees." 형식으로 출력한다.

시간 복잡도

1. DFS 탐색
   • 모든 노드를 순회하며 DFS를 수행하므로, DFS의 시간 복잡도는 O(V+E)이다.
   • N ≤ 500, M ≤ N(N−1)이므로 최악의 경우 O(V^2)가 될 수 있다.
   • 그러나, 실제로는 각 연결 요소마다 DFS가 한 번만 실행되므로 총 탐색 횟수는 제한적이다.
2. 전체 과정
   • 입력 처리: O(V+E)
   • DFS 탐색: O(V+E)
   • 출력 처리: O(1) (트리 개수에 따른 문자열 출력)
   • ⇒ 총 시간 복잡도: O(V+E)

• 최악의 경우
  • V=500, E=500×499 / 2≈124750 일 때,
  • 시간 복잡도는 약 O(125,000) 연산이므로 충분히 해결 가능하다.

정답 코드 (Java)

import java.io.*;  
import java.util.*;  
  
public class Main {  
    private static int N, M, vCnt, eCnt, caseCnt = 0;  
    private static ArrayList<Integer>[] graph;  
    private static boolean[] visited;  
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
      
    public static void main(String[] args) throws IOException {  
        while (true){  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            N = Integer.parseInt(st.nextToken());  
            M = Integer.parseInt(st.nextToken());  
  
            if (N == 0 || M == 0) break; // 종료 조건  
            graph = new ArrayList[N + 1];  
            visited = new boolean[N + 1];  
  
            for (int i = 1; i <= N; i++) {  
                graph[i] = new ArrayList<>();  
            }  
  
            for (int i = 1; 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);  
            }  
  
            solve();  
        }  
  
        bw.flush();  
        bw.close();  
        br.close();  
    }  
  
    private static void solve() throws IOException {  
        caseCnt++;  
        int treeCnt = 0;  
  
        for (int i = 1; i <= N; i++) {  
            if (visited[i]) continue;  
  
            vCnt = 0;  
            eCnt = 0;  
            DFS(i);  
  
            // tree 판정 기준  
            // e == v - 1 인데 양방향이니까 * 2            
            if ( eCnt == 2 * (vCnt - 1)) treeCnt++;  
        }  
  
        bw.write("Case " + caseCnt + ": ");  
  
        switch (treeCnt){  
            case 0:  
                bw.write("No trees.");  
                break;  
            case 1:  
                bw.write("There is one tree.");  
                break;  
            default:  
                bw.write("A forest of "+ treeCnt + " trees.");  
        }  
        bw.newLine();  
    }  
  
    private static void DFS(int cur) {  
        vCnt++; // vertex(node)  개수 count        
        eCnt += graph[cur].size(); // 해당 노드에 연결된 edge 수  
        visited[cur] = true;  
  
        for (int next : graph[cur]) {  
            if (!visited[next]) {  
                DFS(next);  
            }  
        }  
    }  
}