백준 4803번 - 트리

트리 문제 바로 가기

풀이 날짜: 2026-04-09

baekjoon 알고리즘 문제 풀이

풀이 코드

case_num = 1

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

    parent = [0] * (n + 1)

    def find_parent(x):
        if parent[x] != x:
            parent[x] = find_parent(parent[x])
        return parent[x]

    def union(a, b):
        a = find_parent(a)
        b = find_parent(b)

        if a == b:
            parent[a] = 0
        else:
            if a < b:
                if b != 0:
                    parent[b] = a
            else:
                if a != 0:
                    parent[a] = b

    for i in range(1, n + 1):
        parent[i] = i

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

        ra = find_parent(a)
        rb = find_parent(b)

        if ra == rb:
            parent[ra] = 0
        else:
            if ra == 0 or rb == 0:
                parent[ra] = 0
                parent[rb] = 0
            else:
                union(ra, rb)

    tree_set = set()

    for i in range(1, n + 1):
        root = find_parent(i)
        if root != 0:
            tree_set.add(root)

    tree_count = len(tree_set)

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

    case_num += 1
  

접근 방법

단순히 트리 개수를 세는 문제처럼 보이지만, 실제로는 연결 요소와 사이클 판별을 함께 해야 해서 생각보다 까다롭게 느껴졌다. 특히 나는 처음에 “간선이 연결되면 그냥 union 하고, 부모가 같으면 사이클이다” 정도까지만 이해하고 있었는데, 이 문제는 거기서 끝이 아니라 사이클이 한 번이라도 생긴 연결 요소 전체를 트리가 아닌 집합으로 처리해야 한다는 점이 어려웠다. 그래서 단순 유니온 파인드 문제라기보다, 그래프 안에서 각 연결 요소가 트리 조건을 만족하는지 끝까지 추적해야 하는 문제라고 느꼈다.

핵심 아이디어

이 문제의 핵심은 각 연결 요소가 트리인지 판단하는 것이다. 트리는 기본적으로 연결되어 있으면서 사이클이 없어야 한다. 따라서 어떤 정점들이 서로 연결되어 하나의 집합을 이루고 있어도, 그 안에 사이클이 한 번이라도 생기면 그 연결요소는 더 이상 트리가 아니다. 나는 처음에 연결 요소의 개수만 세면 되는 줄 알았는데, 실제로는 연결 요소마다 “이 집합이 정상적인 트리인가?”를 따로 구분해야 했다. 결국 이 문제는 단순한 집합 합치기가 아니라, 집합의 성질까지 관리해야 했다.

내가 가장 헷갈렸던 부분: 루트와 부모 개념

가장 어려웠던 부분은 역시 루트(root) 개념이었다. 유니온 파인드에서 부모 배열을 사용할 때, 각 노드는 자기보다 위에 있는 부모를 가리키고, 최종적으로 가장 위에 있는 대표 노드를 루트라고 본다. 예를 들어 1, 2, 3이 하나의 집합이라면, 실제로는 2의 부모가 1이고 3의 부모도 1인 식으로 연결될 수 있고, 이때 1이 그 집합의 루트가 된다. 나는 처음에 이 루트가 그냥 “가장 작은 번호” 정도로만 느껴졌는데, 실제로는 그 집합 전체를 대표하는 기준점이라는 개념으로 이해해야 했다. 즉, find_parent(x)를 했을 때 나오는 값은 단순히 부모 하나를 찾는 것이 아니라, x가 속한 집합의 대표자를 찾는 과정이었다.

왜 부모가 같으면 사이클인지

이 문제를 이해하는 데 중요했던 부분은 “왜 부모가 같으면 사이클인가?”였다. 두 정점 a, b를 연결하려고 할 때, 이미 find_parent(a)와 find_parent(b)가 같다는 것은 두 정점이 원래부터 같은 연결 요소 안에 있었다는 뜻이다. 그런데 그런 두 점을 다시 간선으로 연결하면, 이미 이어져 있던 길 외에 새로운 길이 하나 더 생기는 셈이므로 결국 원형 구조가 생긴다. 이것이 바로 사이클이다. 즉, 유니온 파인드에서는 같은 루트를 가진 두 정점을 또 연결하려는 순간 사이클이 발생한다고 판단할 수 있다.

어려웠던 이유

단순히 “사이클이 생겼다”에서 끝나지 않는다. 사이클이 생긴 연결 요소 전체를 트리가 아닌 집합으로 처리해야 한다는 점이 어려웠다. 예를 들어 어떤 집합에서 한 번 사이클이 생기면, 그 뒤에 다른 정점이 그 집합에 추가되더라도 그 연결 요소는 여전히 트리가 아니다. 나는 처음에 “사이클 생긴 간선만 제외하면 되는 것이 아닌가”라고 생각했는데, 그게 아니라 그 집합 전체의 상태 자체가 ‘트리가 아님’으로 바뀐다는 점을 놓치고 있었다.

루트를 0으로 두자!

사이클이 발생한 집합의 루트를 0으로 표시했다. 0은 “정상적인 트리가 아닌 집합”이라는 표식 역할을 한다. 예를 들어 어떤 연결 요소에서 사이클이 생기면 그 루트를 0으로 바꿔 버리고, 이후 그 집합과 연결되는 다른 정점들도 결국 0루트를 따라가게 만들면 된다. 이렇게 하면 나중에 전체 정점을 돌면서 루트를 찾았을 때, 루트가 0이 아닌 집합만 세면 트리 개수만 깔끔하게 구할 수 있다.

마지막에 트리 개수를 세는 방식

모든 간선을 처리한 뒤에는 각 정점의 최종 루트를 확인하고, 루트가 0이 아닌 연결 요소만 세어야 한다. 여기서 중요한 건 같은 루트를 여러 번 세면 안 되므로 set을 사용해 중복을 제거하는 것이다. 예를 들어 1, 2, 3이 같은 트리라면 세 정점 모두 루트가 1로 나올 수 있으니, 이를 집합에 넣으면 {1} 하나만 남는다. 반대로 사이클이 있는 집합이라면 루트가 0이 되므로 세지 않는다. 이 과정을 이해하고 나니까, “결국 이 문제는 연결 요소를 세는 문제인데, 그중에서 트리인 것만 고르는 문제”라는 구조가 보였다.

처음에는 단순히 트리 개수만 세면 되는 문제라고 생각했지만, 실제로는 연결 요소와 사이클 여부를 함께 관리해야 해서 생각보다 훨씬 까다로웠다. 특히 유니온 파인드에서 루트가 어떤 의미를 가지는지, 그리고 사이클이 생긴 집합을 왜 별도로 표시해야 하는지를 이해하는 과정이 가장 어려웠다. 하지만 이 문제를 정리하면서 트리의 조건과 유니온 파인드의 활용 방식을 더 분명하게 이해할 수 있었고, 앞으로 비슷한 그래프 문제를 풀 때도 큰 도움이 될 것 같다.