[Python] 4803번 트리

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

4803번: 트리

---

 

24/03/24

 

 

여러 방법으로 풀 수 있는 좋은 문제다.

 

나의 경우는 BFS로 먼저 접근했고, 이후 유니온 파인드로 다시 풀었다.

---

 

첫 번째 문제 접근 방식:

 

 

BFS로 접근했다.

 

그러면 사이클을 어떻게 판단해야 할 지가 문제인데, 사이클 판단을 굳이 할 이유가 없었다.

 

왜냐하면 결국 우리는 트리의 개수를 세야 하고, 트리는 간선의 개수가 $N-1$개이면 노드의 개수가 $N$개임을 알고 있기 때문이다.

 

우리는 하나의 정점을 잡고 BFS를 진행할 때 노드의 개수를 셀 수 있다. 또한, 어떤 정점과 인접한 정점을 탐색하려고 할 때, 어떤 정점에 달려있는 간선들의 개수를 셀 수 있다.

 

어떤 정점을 $i$, $i$와 인접한 정점을 $j$라고 하자. BFS를 진행할 때 $i$와 인접하면서 방문하지 않은 정점 $j$를 큐에 담는데, $j$를 다시 큐에서 뽑을 때 $i$가 인접한 정점이므로, $i$와 $j$를 잇는 간선은 총 $2$번 카운팅 됨을 알 수 있다.

 

따라서 어떤 정점과 인접한 정점을 탐색하려고 할 때 간선의 개수를 세었다면, 실제 간선의 개수는 그것의 절반임을 알 수 있다.

 

이를 통해 간선의 개수와 정점의 개수를 한 번 탐색할 때 알 수 있으며, 이 둘이 하나만큼 차이가 난다면 트리라고 간주할 수 있다.

 

이를 통해 트리의 개수를 쉽게 셀 수 있다. 출력 형식에 맞추어서 출력하는 것에 유의하자.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4803번 트리
# BFS
import sys
input = sys.stdin.readline
from collections import deque

def BFS(visited, graph, start):
    visited[start] = 1
    q = deque()
    q.append(start)
    edges = 0
    nodes = 0
    while q:
        node = q.popleft()
        nodes += 1
        for near_node in graph[node]:
            edges += 1
            if visited[near_node] == 0:
                visited[near_node] = 1
                q.append(near_node)
    edges //= 2
    if edges == nodes-1:
        return True, visited, graph
    else:
        return False, visited, graph

def solve(case_num, N, M):
    visited = [0 for _ in range(N+1)]
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        i, j = map(int, input().split())
        graph[i].append(j)
        graph[j].append(i)
    tree_num = 0
    for node in range(1, N+1):
        if visited[node] == 0:
            is_tree, visited, graph = BFS(visited, graph, node)
            if is_tree: tree_num += 1
    if tree_num == 0:
        print(f'Case {case_num}: No trees.')
    elif tree_num == 1:
        print(f'Case {case_num}: There is one tree.')
    else:
        print(f'Case {case_num}: A forest of {tree_num} trees.')

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

---

 

두 번째 문제 접근 방식:

 

 

유니온 파인드로 접근했다.

 

유니온 파인드로 사이클을 찾아낼 수 있다.

 

두 정점을 이었을 때 사이클이 되는 경우는, 두 정점을 이으려고 할 때 이미 두 정점의 부모가 같은 경우이다.

 

또한, 사이클에 더 간선을 단다고 해서 트리가 되진 않는다.

 

사이클을 이루는 정점의 부모를 저장하는 집합 cycle을 정의했다.

 

간선을 입력받을 때 마다 두 정점의 부모를 조사했다.

 

두 정점을 이으려고 할 때 이미 두 정점의 부모가 같은 경우와, 두 정점의 부모 중 하나가 이미 cycle에 있는 경우, 두 경우에 대해, cycle에 두 정점의 부모를 모두 담아주었다.

 

이후 두 정점을 union해주었다.

 

이를 통해 cycle에는 cycle을 이루는 정점의 부모들이 담겨있음을 알 수 있다.

 

parent배열도 find연산을 해주고, set을 통해 중복을 제거했다. 이후, 중복 제거한 parent set과 cycle set을 차집합 연산을 통해 빼주고 그 길이를 구했다.

 

parent배열은 0부터 시작하는 배열이고, 0은 어느 곳에도 이어진 정점이 아니므로 최종적으로 구한 길이에 1을 빼준 값이 답이 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 4803번 트리
# 유니온 파인드
import sys
input = sys.stdin.readline

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

def union(node1, node2):
    p1, p2 = find(node1), find(node2)
    if p1 < p2:
        parent[p2] = p1
    else:
        parent[p1] = p2

case_num = 1
while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    parent = list(range(N+1))
    cycle = set()
    for _ in range(M):
        i, j = map(int, input().split())
        pi, pj = find(i), find(j)
        if pi == pj or pi in cycle or pj in cycle:
            cycle.add(pi)
            cycle.add(pj)
        union(i, j)
    for i in range(N+1):
        find(i)
    tree_num = len(set(parent)-set(cycle))-1
    if tree_num == 0:
        print(f'Case {case_num}: No trees.')
    elif tree_num == 1:
        print(f'Case {case_num}: There is one tree.')
    else:
        print(f'Case {case_num}: A forest of {tree_num} trees.')
    case_num += 1