[BOJ] 백준 4083번 트리(Python)

문제

그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.

트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다.
• 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다.
• 같은 간선은 여러 번 주어지지 않는다.
• 정점은 1번부터 n번까지 번호가 매겨져 있다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

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

예제

입력

6 3
1 2
2 3
3 4
6 5
1 2
2 3
3 4
4 5
5 6
6 6
1 2
2 3
1 3
4 5
5 6
6 4
0 0

출력

Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.

풀이

from collections import deque

def check(num):					# num으로 받은 노드가 트리인지 확인하는 함수
    visited[num] = True				# 이제 방문함.
    queue = deque([num])			# BFS를 위한 queue

    while queue:
        node = queue.popleft()			# 노드 가져옴
        for n_node in trees[node]:              # bfs. 해당 노드에 연결된 노드들 차례로 가져옴.
            if trees[node][n_node] == 0:        # 엣지 체크 (0: 체크 안함, 1: 체크함)
                if not visited[n_node]:         # 해당 노드에 처음 방문
                    visited[n_node] = True
                    queue.append(n_node)        # 대기열에 다음 노드 추가
                    trees[node][n_node] = 1	# 엣지 체크
                    trees[n_node][node] = 1	# 엣지 체크
                else:
                    return False                # 헤당 노드에 방문한 적이 있으므로 이는 트리가 아닌 그래프
    return True

test = 0
while True:
    test += 1
    N, M = map(int, input().split())
    if N == 0 and M == 0:			# 0 0 입력시 종료
        break
    edges = [list(map(int, input().split())) for _ in range(M)]
    visited = [False] * (N + 1)			# 방문여부 확인용
    trees = [{} for _ in range(N+1)]		# 노드 별 연결된 엣지 모음
    for e in edges:
        trees[e[0]][e[1]] = 0           	# 엣지 체크. 0: 체크X / 1: 체크 O
        trees[e[1]][e[0]] = 0

    cnt = 0					# 트리 갯수
    for num in range(1, N + 1):			# 모든 노드 확인
        if not visited[num]:			# 해당 노드 방문 안한 경우
            if check(num):			# 트리인지 체크함
                cnt += 1

    # 출력
    print("Case {}: ".format(test), end="")
    if cnt == 0:
        print("No trees.")
    elif cnt == 1:
        print("There is one tree.")
    else:
        print("A forest of {} trees.".format(cnt))

python3로 제출하면 시간 초과가 나오고 pypy3로 제출하면 잘 된다.
python3로 하는 방법이 있을지 공부해봐야 함.