[알고리즘|파이썬] 백준 4803 트리
문제 링크: https://www.acmicpc.net/problem/4803
📌 문제 탐색하기
시간 제한: 1초
메모리 제한: 256 MB
✏️ 구해야 하는 정답
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.
트리의 특징
- 트리는 사이클이 없는 연결 요소이다.
- 트리는 정점이 n개, 간선이 n-1개 있다.
- 임의의 두 정점에 대해서 경로가 유일하다.
조건
- n ≤ 500
- m ≤ n(n-1)/2
- 입력의 마지막 줄에는 0이 두 개 주어진다.
출력 값
- 그래프에 트리가 없다면 "No trees."
- 한 개라면 "There is one tree."
- T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력
📌 풀이하기
예제 1.
6 3 # case#1
1 2
2 3
3 4
6 5 # case#2
1 2
2 3
3 4
4 5
5 6
6 6 # case#3
1 2
2 3
1 3
4 5
5 6
6 4
0 0 # end
주어진 3개의 케이스에 대해 각 케이스 트리를 표현하면 위와 같다.
조건으로 주어진 트리의 특징의 조건에 맞는 개수를 구하면 된다.
트리의 특징
- 트리는 사이클이 없는 연결 요소이다.
- 트리는 정점이 n개, 간선이 n-1개 있다.
- 임의의 두 정점에 대해서 경로가 유일하다.
✏️ 문제를 어떻게 풀 것인가?
1️⃣ 그래프를 인접 리스트 형태로 표현
주어진 M개의 간선 정보를 통해 양방향 그래프를 구성한다.
graph[A].add(B)
graph[B].add(A)
2️⃣ BFS 탐색으로 요소 개수 탐색
- 탐색한 정점 개수 확인 (node)
- 탐색한 간선 개수 확인 (edge)
--> node -1 == edge
- 탐색 중 방문했던 노드를 다시 방문하는 경우(사이클 존재 여부)
--> false
3️⃣ 출력
- tree == 0 -> "No trees."
- tree == 1 -> "There is one tree."
- tree > 1 -> "A forest of T trees."를 테스트 케이스 번호와 함께 출력
📌 코드 설계하기
1. n(정점 개수)과 m(간선 개수)을 입력
-> 입력의 마지막 줄은 0 0이므로, n == 0이고 m == 0이면 프로그램을 종료
2. 양방향 그래프 구성
- graph를 인접 리스트 형태로 생성
- 정점 번호는 1번부터 n번까지이므로 graph = [[] for _ in range(n + 1)]으로 초기화
- graph[i].append(j), graph[j].append(i)
3. bfs 탐색 사용하여 연결 요소 찾기
- visited = [False] * (n + 1) 리스트를 생성하여 각 정점의 방문 여부를 저장
- 모든 정점(1번부터 n번까지)에 대해 아직 방문하지 않았다면 BFS를 수행하여 연결 요소(서브 그래프)를 탐색
- bfs():
1. queue에 시작 정점을 추가하고, visited[start] = True로 방문 처리
2. nodes(정점 개수)와 edges(간선 개수)를 0으로 초기화
3. 큐에서 정점을 하나씩 꺼내면서 연결된 정점을 확인
a. 방문하지 않은 정점이면 큐에 추가하고 방문 처리
b. 간선 개수를 증가시키는데, 무방향 그래프이므로 모든 간선이 두 번씩 카운트되므로 마지막에 edges //= 2로 보정
4. node -1 == edge 조건 확인
- 조건 충족 시 tree_count += 1
5. 출력 포맷에 맞게 결과 출력
- tree == 0 -> "No trees."
- tree == 1 -> "There is one tree."
- tree > 1 -> "A forest of T trees."를 테스트 케이스 번호와 함께 출력
📌 정답 코드
import sys
from collections import deque
def bfs(start, graph, visited):
queue = deque([start])
visited[start] = True
nodes, edges = 0, 0
while queue:
node = queue.popleft()
nodes += 1
for neighbor in graph[node]:
edges += 1
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
edges //= 2
return nodes, edges
case_num = 1
while True:
n, m = map(int, sys.stdin.readline().split())
if n == 0 and m == 0:
break
graph = [[] for _ in range(n + 1)]
for _ in range(m):
i, j = map(int, sys.stdin.readline().split())
graph[i].append(j)
graph[j].append(i)
visited = [False] * (n + 1)
tree_count = 0
for node in range(1, n + 1):
if not visited[node]:
nodes, edges = bfs(node, graph, visited)
if edges == nodes - 1:
tree_count += 1
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