[골드 4] 백준 4803 - 트리 (파이썬)

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

풀이

• 정점 N개와 간선 M개로 구성된 무방향 그래프가 주어진다.
• 그래프 내에 트리가 몇 개 존재하는지 출력해야 한다.
• 트리의 정의: 사이클이 없는 연결 그래프
  • 간선 수 = 정점 수 - 1 이면 트리다.

adj = [[] for _ in range(N)]

인접 리스트를 생성한다. 단 정점번호는 0부터 N - 1이다.

for _ in range(M) :
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

무방향 간선이므로 양쪽에 모두 추가한다.

입력은 1-based이지만 내부는 0-based로 처리한다.

visit = [False] * N
queue = deque()

num_trees = 0

방문 여부 체크를 위한 배열을 미리 초기화 하고, num_trees는 트리 개수 카운트를 위해 초기화 한다.

for i in range(N) :
    if not visit[i] :

방문하지 않은 정점이 있다면 새로운 연결 요소를 탐색 하기 시작한다.

queue.append(i)
visit[i] = True
num_nodes = 1
num_edges = 0

BFS를 준비하기 위해서 노드 개수는 1개부터 시작하며 간선 개수는 0으로 초기화 한다.

while len(queue) != 0 :
    u = queue.popleft()

    for v in adj[u] :
        num_edges += 1
        if not visit[v] :
            queue.append(v)
            visit[v] = True
            num_nodes += 1

BFS로 연결된 노드를 탐색하고, 간선을 셀때는 adj[u]에서 연결된 모든 v에 대해서 num_edges += 1을 하기 때문에 각 간선이 양쪽 노드에서 두번 카운트 된다.

즉, 마지막에 num_edges //= 2 또는 num_edges /= 2를 해줘야한다.

num_edges /= 2
if num_edges == num_nodes - 1 :
    num_trees += 1

print(f"Case {testcase}:", end = " ")
if num_trees == 0 :
    print("No trees.")
elif num_trees == 1 :
    print("There is one tree.")
else :
    print(f"A forest of {num_trees} trees.")

출력 포맷에 맞춰서 케이스 번호와 트리수에 따라 적절하게 출력한다.

코드

# 백준 4803 - 트리
# 분류 : 트리

import sys
from collections import deque

input = sys.stdin.readline

testcase = 1

while True :
    N, M = map(int, input().split())
    if N == 0 and M == 0 :
        break

    adj = [[] for _ in range(N)]

    for _ in range(M) :
        a, b = map(int, input().split())
        a -= 1
        b -= 1

        adj[a].append(b)
        adj[b].append(a)
    
    visit = [False] * N
    queue = deque()

    num_trees = 0
    for i in range(N) :
        if not visit[i] :
            queue.append(i)
            visit[i] = True

            num_nodes = 1
            num_edges = 0

            while len(queue) != 0 :
                u = queue.popleft()

                for v in adj[u] :
                    num_edges += 1
                    if not visit[v] :
                        queue.append(v)
                        visit[v] = True
                        num_nodes += 1

            num_edges /= 2
            if num_edges == num_nodes - 1 :
                num_trees += 1
    
    print(f"Case {testcase}:", end = " ")
    if num_trees == 0 :
        print("No trees.")
    elif num_trees == 1 :
        print("There is one tree.")
    else :
        print(f"A forest of {num_trees} trees.")

    testcase += 1