[파이썬/Python] 백준 4803번: 트리

📌 문제 : 백준 4803번

---

📌 문제 탐색하기

n : 정점 개수 $(1 ≤ n ≤ 500)$
m : 간선 개수 $(m ≤ \frac{n(n-1)}{2})$

서로 다른 m개의 간선을 입력받아 트리가 몇 개인지 세는 문제이다.

문제 풀이

연결된 노드를 탐색하면서 트리의 특징을 이용해 트리인지 아닌지 확인해 개수를 세면 될 것 같다.

⭐️ 트리는 사이클이 없어야 한다.

이를 활용해 각 정점과 그에 연결된 정점들을 DFS로 탐색하면서 트리를 확인한다.
연결된 노드를 탐색했을 때 부모 노드 외에 이미 방문했던 노드에 한번 더 연결되어있다는 것은 사이클이 있음을 의미한다❗️

⭐️ 사이클 확인 방법

• for문으로 연결된 노드들을 확인한다.
• 방문 안한 노드가 있다면 재귀적으로 DFS를 수행한다.
  • 다음 노드에 이용할 부모 노드(현재 노드)를 함께 DFS에 넣어준다.
• 방문한 노드가 있는데 부모 노드가 아니라면?
  • 사이클 존재함을 의미!
  • 트리가 아니라는 것을 반환

가능한 시간복잡도

DFS 수행 → $O(n + m)$
연결 정보 입력 → $O(m)$

최종 시간복잡도
$O(n + m)$로 최악의 경우 $O(n + \frac{n(n-1)}{2}) = O(500 + 124750) = O(125250)$로 1초 내 연산 가능하다.

알고리즘 선택

while문 내에서 DFS로 트리인지 판별해 개수 세기

---

📌 코드 설계하기

1. DFS 구현
2. n, m 입력
3. 케이스 번호 초기화
4. 테스트 케이스 별 작동 구현
   4-1. 종료 조건 정의
   4-2. 트리 저장 그래프 정의
   4-3. 방문 처리 리스트 정의
   4-4. 간선 정보 입력
   4-5. 트리 개수 변수 정의
   4-6. 결과 출력
   4-7. 테스트케이스 수 증가
   4-8. 4번 반복

---

📌 시도 회차 수정 사항

1회차

• 문제 이해를 잘못해서 n, m이 아니라 간선 정보가 0, 0이 들어올 때까지 입력하도록 구현해서 조건을 수정했다.
• 테스트케이스 개수를 고려해야주어야 한다는 것을 생각 못했다. 따라서 모든 코드들을 while문 내에서 돌아가도록 수정했다.

2회차

• while문 내에 조건이 n, m이 0이 입력될 때까지 반복하는 것이다. n, m은 반복문 밖에서 입력받기 때문에 같은 결과가 테스트 케이스만큼 반복해 출력되었다.
• n, m 입력받는 부분을 while문 안으로 옮겼다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# DFS 구현
def dfs(v, parent):
    visited[v] = 1
    # 연결 노드 확인
    for i in tree[v]:
        if not visited[i]:
            # 연결 끝까지 확인
            if not dfs(i, v):
                return False
        # 방문한 노드인데 부모 노드 아니라면 트리 아님
        elif i != parent:
            return False
    return True


# 케이스 번호 초기화
case = 1

# 간선 정보 입력
while True:
    # n, m 입력
    n, m = map(int, input().split())

    # 종료 조건
    if n == 0 and m == 0:
        break

    # 트리 저장 그래프 정의
    tree = [[] for _ in range(n + 1)]

    # 방문 처리 리스트 정의
    visited = [0] * (n + 1)

    # 간선 정보 입력
    for _ in range(m):
        a, b = map(int, input().split())
        # 정보 저장
        tree[a].append(b)
        tree[b].append(a)

    # 트리 개수 변수 정의
    count = 0

    # DFS 수행
    for i in range(1, n + 1):
        if not visited[i]:
            if dfs(i, -1):
                count += 1

    # 결과 출력
    if count == 0:
        print(f'Case {case}: No trees.')

    elif count == 1:
        print(f'Case {case}: There is one tree.')

    else:
        print(f'Case {case}: A forest of {count} trees.')

    # 테스트 케이스 수 증가
    case += 1

• 결과
  

---

📌 정리

👑 트리 (tree)

• 노드 & 에지로 연결된 그래프의 특수한 형태
• 특징
  • 순환 구조(cycle) ❌
  • 루트 노드 1개 존재 → 나머지 노드는 단 1개의 부모 노드 가짐
  • 부분 트리(subtree) → 트리의 모든 특징 가짐

🤖 트리 구성 요소

구성 요소	설명
노드	데이터의 index & value 포함 요소
에지	노드 - 노드 간 연결 관계 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드 해당 노드
자식 노드	두 노드 사이의 관계에서 하위 노드 해당 노드
리프 노드	트리에서 가장 하위에 존재하는 노드 (자식 노드 X)
서브 트리	전체 트리에 속한 작은 트리