[백준/Python]4803: 트리

문제

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

백준 단계별로 풀어보기 - 트리

---

풀이

입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

 

정말 어처구니 없는 실수로 삽질했던 문제다;;

 

입력값으로 주어지는 간선은 '노드1 노드2' 의 형태로 되어있는데, 부모-자식 순서로 주어지는게 아니다.

놀랍지만 이 실수로 거진 20분은 삽질한것같다.(이게 안될리가 없는데 왜 안되지?의 반복)

 

 

일단 간선들을 저장할 2차원 리스트를 생성해준다. 각 행에는 빈 리스트가 들어간다.

lst = [[], [], []] ← 이런 형태가 되겠다.

그리고 무방향 그래프이므로, 양방향으로 저장해준다.

 

그리고 주어진 그래프는 여러개의 트리가 있을수도, 하나의 트리만 있을수도, 트리가 아예 없을수도 있다.

따라서 BFS를 여러번 실행해야 한다.

만약 그래프를 탐색 중 방문하지 않은 노드가 발견된다면, 해당 노드를 시작점으로 BFS를 실행한다.

 

BFS를 실행하며 노드의 수, 간선의 수를 저장한 뒤 마지막에 트리 조건에 부합하는지 체크한다.

❗트리의 조건: 간선의 수는 노드의 수-1 이어야 함.

 

참고로 간선의 수는 //2를 해줘야 한다. 양방향으로 저장해줬기 때문이다.

 

조건을 만족한다면 True, 아니라면 False를 반환하고,

방문하지 않은 노드가 나올때까지 마저 탐색한다.

 

전체 코드

# ⭐ 무방향 그래프로 수정한 결과

# 메모리: 37180KB / 시간: 200ms
import sys
from collections import deque


input = sys.stdin.readline

def bfs(tree, visited, start):
    queue = deque([start])
    visited[start] = True
    node_cnt = edge_cnt = 0

    while queue:
        curr_node = queue.popleft()
        node_cnt += 1

        for node in tree[curr_node]:
            edge_cnt += 1
            if not visited[node]:
                visited[node] = True
                queue.append(node)

    # 간선은 양방향으로 저장되므로 2로 나누어준다.
    edge_cnt //= 2

    # 트리 조건: 간선 수는 정점 수 - 1이어야 함
    return True if edge_cnt == node_cnt-1 else False

order = 1
while True:
    n, m = map(int, input().split())

    if n == 0 and m == 0:
        break

    tree = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        tree[u].append(v)
        tree[v].append(u)  # 양방향 간선 저장

    visited = [False] * (n + 1)
    ret = 0

    for i in range(1, n + 1):
        if not visited[i]:
            if bfs(tree, visited, i):
                ret += 1

    print(f"Case {order}: ", end="")
    if ret == 0:
        print("No trees.")
    elif ret == 1:
        print("There is one tree.")
    else:
        print(f"A forest of {ret} trees.")

    order += 1