백준 트리 장인 [32340] 파이썬(Python) 코드 + 해설

1.  문제 소개

세종이는 정점 N개와 간선 M개로 이루어진 단순 그래프를 가지고 있다. 그는 이 그래프에 0개 이상의 간선을 추가하여 트리로 만들려고 한다. 간선을 추가할 수 있지만 기존의 간선을 제거할 수는 없다. 간선을 추가하는 방법의 가짓수를 구하고, 그 수가 K를 넘으면 −1을 출력하고, 그렇지 않으면 정확한 가짓수를 출력하는 문제다.

2.  문제 해결 방법

트리의 조건을 고려해보자. 트리는 사이클이 없는 연결 그래프다. 따라서 주어진 그래프를 트리로 만들기 위해서는 다음을 만족해야 한다:

1. 사이클이 없어야 한다: 기존 그래프에 사이클이 있으면 간선만 추가해서 트리로 만들 수 없다. 간선을 제거할 수 없기 때문이다.
2. 연결 그래프여야 한다: 모든 정점이 서로 연결되어 있어야 한다.

따라서 주어진 그래프에서 사이클이 있는 연결 성분이 있다면 트리로 만들 수 없으므로 가짓수는 0이 된다.

그래프가 여러 개의 연결 성분(컴포넌트)으로 이루어진 경우, 각 컴포넌트는 사이클이 없는 트리여야 한다. 그렇다면 각 컴포넌트를 서로 연결하여 전체 그래프를 하나의 트리로 만들 수 있다.

2-1. 사이클 탐지 개선:

기존의 사이클 탐지 방식에서 문제가 있었다. 사이클을 정확하게 감지하기 위해 각 컴포넌트의 간선 수를 유지해야 한다. 각 컴포넌트에서 간선 수가 정점 수보다 많으면 사이클이 존재한다.

2-2. 가짓수 계산 방법:

• 컴포넌트 수 c를 계산한다.
• 각 컴포넌트의 크기 𝑠𝑖​를 구한다.
• 전체 가짓수는 𝑁𝑐−2×∏𝑖=1𝑐𝑠𝑖​로 계산한다.
• 가짓수가 K를 넘으면 −1을 출력하고, 그렇지 않으면 정확한 가짓수를 출력한다.

2-3. 구현 세부사항:

• 유니온-파인드(Union-Find) 자료구조를 사용하여 연결 성분을 관리하고 사이클을 감지한다.
• 각 컴포넌트의 간선 수를 유지하여 사이클 존재 여부를 정확하게 판단한다.

3.  백준 트리 장인 32340 파이썬(Python) 정답 코드

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

N, M, K = map(int, input().split())
parent = [i for i in range(N+1)]
size = [1] * (N+1)
edge_count = [0] * (N+1)

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    ru = find(u)
    rv = find(v)
    if ru != rv:
        parent[rv] = ru
        size[ru] += size[rv]
        edge_count[ru] += edge_count[rv] + 1
    else:
        edge_count[ru] += 1

for _ in range(M):
    u, v = map(int, input().split())
    union(u, v)

components = {}
for i in range(1, N+1):
    root = find(i)
    if root not in components:
        components[root] = (size[root], edge_count[root])

for root, (s, e) in components.items():
    if e != s - 1:
        print(0)
        sys.exit()

c = len(components)
total_ways = 1

if c == 1:
    print(1)
    sys.exit()

for _ in range(c - 2):
    total_ways *= N
    if total_ways > K:
        print(-1)
        sys.exit()

for s, _ in components.values():
    total_ways *= s
    if total_ways > K:
        print(-1)
        sys.exit()

print(total_ways)

4.  32340 트리 장인 정답 코드 해설

1. 입력 및 초기화:
   • N, M, K를 입력받는다.
   • 각 정점의 부모를 자기 자신으로 초기화한다.
   • 각 컴포넌트의 크기 size와 간선 수 edge_count를 저장할 배열을 초기화한다.
2. 유니온-파인드 구현:
   • find(u): 경로 압축(Path Compression)을 사용하여 정점 u의 대표 노드를 찾는다.
   • union(u, v): 정점 u와 v를 연결한다.
     • 두 정점의 대표 노드가 다르면 두 집합을 합치고, 간선 수와 사이즈를 업데이트한다.
     • 두 정점의 대표 노드가 같으면 사이클이 발생한 것이므로 해당 컴포넌트의 edge_count를 증가시킨다.
3. 간선 처리 및 사이클 탐지:
   • 모든 간선을 처리하면서 union(u, v)를 수행한다.
   • 각 컴포넌트의 간선 수를 정확하게 유지하여 사이클 존재 여부를 판단한다.
4. 컴포넌트 정보 수집:
   • 모든 정점에 대해 대표 노드를 찾아 컴포넌트별로 크기와 간선 수를 저장한다.
   • 컴포넌트 내의 간선 수와 정점 수를 비교하여 사이클 존재 여부를 확인한다.
     • 만약 간선 수가 정점 수보다 많으면 사이클이 존재하므로 0을 출력하고 종료한다.
5. 가짓수 계산:
   • 컴포넌트 수 c를 계산한다.
   • 컴포넌트 수가 1인 경우:
     • 이미 연결된 트리이므로 방법의 수는 1이다.
   • 컴포넌트 수가 2 이상인 경우:
     • 먼저 𝑁^{𝑐−2}를 계산한다. 이때, 곱셈 과정에서 가짓수가 K를 넘으면 −1을 출력하고 종료한다.
     • 각 컴포넌트의 크기를 곱해준다. 이때도 가짓수가 K를 넘으면 −1을 출력한다.
6. 결과 출력:
   • 가짓수가 K를 넘지 않으면 정확한 가짓수를 출력한다.

5.  32340 트리 장인 제출 결과

32340 제출 결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.