BaekJoon 4803번 : 트리 (python)

BaekJoon 4803번 : 트리 (G4 32.231%)

트리 문제

주어진 그래프가 트리인지 판별하는 문제로 단계별 풀이 '트리'의 마지막 문제이다.

• 이 문제에서 주어진 조건은 트리는 사이클이 없는 연결 요소라고 알려주고 있다. 결국 반복되지 않는 요소들의 집합이고 다른 표현으로 각 원소당 부모 노드를 하나만 가지고 있는 상황이 트리라고 볼 수도 있게 된다.
• 기본적으로 트리를 양방향으로 입력받아 정렬해주고 BFS를 통해 각 원소들을 탐색해주며 방문여부를 확인해준다.
• BFS에서는 아직 방문하지 않은 노드라면 방문표시를 하고 해당 원소의 부모 노드를 설정해준다. 만약 이미 방문했던 노드라면 부모 노드가 정확히 설정되어있는지 체크 해준다. 이 부분에서 parents[x] != i라고 되어있는데 이 부분은 위에서 진행된 트리의 순회를 진행하고 역주행하며 부모 노드가 체크가 잘 되어있는지 체크하는 방식인 것이다. 만약 부모 노드가 아닌데 방문했다면 return값을 False로 바꿔주게 된다.
• 그렇게 이미 방문된 노드들은 BFS를 다시 방문하지 않게 되고 만약 BFS를 다녀온 노드에서 return값이 True일 경우 count를 1 더해주는 방식으로 진행된다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(i) :
    q = deque([i])
    is_check = True
    check[i] = True
    while q :
        x = q.popleft()
        for i in tree[x] :
            if not check[i] :
                q.append(i)
                check[i] = True
                parents[i] = x
            elif parents[x] != i:
                is_check = False 
    return is_check

Testcase = 0
while True :
    n, m = map(int,input().split())
    Testcase += 1
    tree = {i : [] for i in range(1, n+1)}
    
    if n == m == 0 :
        break
    for _ in range(m) :
        a, b = map(int,input().split())
        tree[a].append(b)
        tree[b].append(a)
        
    count = 0
    check = [False] * (n+1)
    parents = [0] * (n+1)
    for i in range(1, n+1) :
        if not check[i] and bfs(i):
            count += 1

    if count == 1 :
        print(f'Case {Testcase}: There is one tree.')
    elif count == 0 :
        print(f'Case {Testcase}: No trees.')
    else :
        print(f'Case {Testcase}: A forest of {count} trees.')