Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

28. 트리

대표적인 그래프 종류 중 하나인 트리를 다뤄 봅시다.

Java / Python

7. 트리

4803번

주어진 그래프가 트리인지 판별하는 문제

이번 문제는 그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하는 문제이다.

DFS를 이용해 트리의 사이클이 존재하는 것을 찾아 제외하고 트리의 개수를 찾는다.

• Java

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

public class Main {
	static ArrayList<Integer>[] graph;
	static boolean[] visit;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		int testcase = 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;

			graph = new ArrayList[N + 1];
			visit = 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 v1 = Integer.parseInt(st.nextToken());
				int v2 = Integer.parseInt(st.nextToken());

				graph[v1].add(v2);
				graph[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: ", testcase++));

			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');
		}
		bw.write(sb.toString());

		bw.flush();
		br.close();
		bw.close();
	}

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

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

		for (int n : graph[before]) {
			if (n != cur)
				result &= DFS(n, before);
		}
		return result;
	}
}

• Python

import sys
input = sys.stdin.readline

def dfs(prev, node):
    visited[node] = True # 방문처리
    for n in graph[node]:
        if n == prev:
            continue
        if visited[n]:
            return False
        if not dfs(node, n):
            return False
    return True

tc = 0
while True:
    tc += 1
    N, M = map(int, input().split())
    if [N, M] == [0, 0]: 
        break
    graph = [[] for _ in range(N+1)] 
    visited = [False] * (N+1) # 방문 여부
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b) 
        graph[b].append(a)

    cnt = 0 # 트리의 개수
    for v in range(1, N+1):
        if not visited[v]: # 방문하지 않은 경우만 DFS 수행
            if dfs(0, v):
                cnt += 1 # 사이클이 없는 경우 트리 개수 증가
    if cnt == 0:
        print("Case {}: No trees.".format(tc))
    elif cnt == 1:
        print("Case {}: There is one tree.".format(tc))
    else:
        print("Case {}: A forest of {} trees.".format(tc, cnt))