[BOJ] 트리 - 4803 (G4)
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 (추가 시간 없음) | 256 MB |
문제
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 즉, 트리는 정점 개수가 n개, 간선 개수가 n-1개인 그래프이다.
그래프가 주어졌을 때, 트리의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n과 m이 주어진다. (1 ≤ n ≤ 500, 0 ≤ m ≤ n(n-1)/2) n은 정점의 개수, m은 간선의 개수이다. 다음 m개의 줄에는 간선을 나타내는 두 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다. 정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각 테스트 케이스마다 “Case x:”를 출력한다. (x는 테스트 케이스 번호이고 1부터 시작한다.)
트리의 개수 t가 0이면 “No trees.”를, t가 1이면 “There is one tree.”를, t > 1이면 “A forest of t trees.”를 출력한다.
풀이
이 문제는 주어진 그래프에서 트리가 몇 개 있는지 세는 문제이다. 트리의 조건은 다음과 같다:
- 연결되어 있다 (하나의 연결 요소)
- 사이클이 없다
- 정점이 n개일 때 간선이 n-1개
접근 방법
각 연결 요소를 찾고, 그 연결 요소가 트리인지 확인한다. 트리 판별 방법:
- DFS를 수행하며 사이클이 있는지 확인
- 간선의 개수가 정점의 개수 - 1인지 확인
사이클 판별
DFS를 수행하면서:
- 이미 방문한 노드를 다시 방문하면 (단, 바로 직전 노드 제외) → 사이클 존재
- 모든 노드를 방문했을 때 사이클이 없으면 → 트리 가능성 있음
트리 조건 확인
사이클이 없더라도 간선 수가 정점 수 - 1이어야 트리이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def main():
case_num = 1
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
edges = []
for _ in range(m):
u, v = map(int, input().split())
edges.append((u, v))
graph = [[] for _ in range(n + 1)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * (n + 1)
tree_count = 0
def dfs(cur, prev, nodes, edges):
visited[cur] = True
nodes.add(cur)
for neighbor in graph[cur]:
# 부모 방문 방지
if neighbor == prev:
continue
# 사이클 발견하면 빠져나오기
if visited[neighbor]:
return False
edges.add(tuple(sorted((cur, neighbor))))
if not dfs(neighbor, cur, nodes, edges):
return False
return True
for i in range(1, n + 1):
if not visited[i]:
nodes = set()
edges = set()
# 사이클 확인
if not dfs(i, 0, nodes, edges):
continue
# 사이클이 없고, 간선의 수가 노드의 수 - 1이면 트리
if len(edges) == len(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
if __name__ == "__main__":
main()
코드 설명
그래프 구성
1
2
3
4
graph = [[] for _ in range(n + 1)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
- 인접 리스트로 양방향 그래프 구성
DFS 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dfs(cur, prev, nodes, edges):
visited[cur] = True
nodes.add(cur)
for neighbor in graph[cur]:
# 부모 방문 방지
if neighbor == prev:
continue
# 사이클 발견하면 빠져나오기
if visited[neighbor]:
return False
edges.add(tuple(sorted((cur, neighbor))))
if not dfs(neighbor, cur, nodes, edges):
return False
return True
cur: 현재 노드prev: 직전에 방문한 노드 (부모 노드)nodes: 현재 연결 요소의 정점 집합edges: 현재 연결 요소의 간선 집합
사이클 판별 로직:
neighbor == prev: 바로 직전 노드는 무시 (양방향 간선)visited[neighbor]: 이미 방문한 노드를 다시 만나면 사이클- 사이클이 발견되면
False반환
트리 개수 세기
1
2
3
4
5
6
7
8
9
10
11
12
for i in range(1, n + 1):
if not visited[i]:
nodes = set()
edges = set()
# 사이클 확인
if not dfs(i, 0, nodes, edges):
continue
# 사이클이 없고, 간선의 수가 노드의 수 - 1이면 트리
if len(edges) == len(nodes) - 1:
tree_count += 1
- 방문하지 않은 각 연결 요소에 대해 DFS 수행
- 사이클이 없고
간선 수 = 정점 수 - 1이면 트리로 카운트
출력 형식
1
2
3
4
5
6
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.")
- 트리 개수에 따라 다른 형식으로 출력
시간 복잡도
- 각 테스트 케이스마다:
- 그래프 구성: O(m)
- DFS 탐색: O(n + m)
- 전체: O(n + m)
n ≤ 500, m ≤ n(n-1)/2이므로 충분히 빠르게 해결할 수 있다.
트리의 성질
트리는 다음 조건 중 하나를 만족한다:
- n개의 정점과 n-1개의 간선을 가지며 사이클이 없다
- 임의의 두 정점 사이에 경로가 정확히 하나 존재한다
- 간선을 하나 제거하면 두 개의 연결 요소로 분리된다
- 사이클이 없지만 간선을 하나 추가하면 사이클이 생긴다
이 문제에서는 1번 조건을 사용하여 트리를 판별한다.
주의 사항
- 양방향 간선: DFS에서 직전 노드로 돌아가는 것은 사이클이 아니다.
- 간선 중복 방지: 간선을
set에 저장할 때 정렬하여 (u, v)와 (v, u)를 같은 간선으로 처리한다. - 연결 요소 분리: 각 연결 요소를 독립적으로 판별해야 한다.
- 출력 형식: 트리 개수에 따라 정확한 문구를 출력해야 한다.
다른 접근 방법
Union-Find를 사용하여 더 효율적으로 해결할 수도 있다. Union 연산 중 이미 같은 집합에 속한 노드를 연결하려 하면 사이클이 생긴다는 점을 이용한다.