백준 4803번: 트리 (Python, PyPy3)

접근

서로 연결된 '연결 요소'가 싸이클을 이루는지 아닌지 체크하여 싸이클이 아닌 연결 요소의 개수를 세어주면 된다. 주의할 점은 다른 정점에 연결되지 않은 외딴 정점 또한 트리의 조건에 부합한다는 것이다.

한개의 연결 요소가 싸이클을 이루는지 체크하는 방법으로 BFS 알고리즘을 사용하였다.

1. 첫번째 정점부터 탐색하면서 현재 정점의 visited를 체크하고 False라면 True로 갱신해준다.
2. 첫번째 정점에서 연결된 정점들을 탐색하면서 visited가 False라면 queue에 추가해준다.
3. 탐색을 진행하면서 queue에서 꺼내온 현재 정점의 visited가 True라면 이미 지나온 다른 요소와 다른 방법으로 연결되어 있으므로 (싸이클을 이루므로) tree로 카운트하지 않는다.
4. queue를 모두 탐색했는데 싸이클을 이루는 요소가 없다면 tree를 카운트해준다.

코드

import sys


def bfs(x):
    isTree = True
    q = [x]
    while q:
        now = q.pop(0)
        if visited[now] == 1:  # 현재 정점을 이미 다른 요소를 통해 방문했다면(싸이클을 이룬다면)
            isTree = False  # 트리가 아님을 표시해준다.
        visited[now] = 1
        for j in graph[now]:
            if visited[j] == 0:
                q.append(j)
    return isTree


case = 0
while True:
    case += 1
    n, m = map(int, sys.stdin.readline().split())
    if [n, m] == [0, 0]:  # 탈출 조건
        break
    graph = [[] for _ in range(n + 1)]  # 서로 연결된 요소 저장
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    treeCnt = 0  # 케이스 별 트리의 개수
    visited = [0] * (n + 1)
    for i in range(1, n + 1):
        if visited[i] == 1:  # 방문한적 있다면 패스
            continue
        if bfs(i) is True:  # 현재의 연결 요소가 tree 라면 카운트
            treeCnt += 1
    if treeCnt == 0:
        print('Case {}: No trees.'.format(case))
    elif treeCnt == 1:
        print('Case {}: There is one tree.'.format(case))
    else:
        print('Case {}: A forest of {} trees.'.format(case, treeCnt))

더 생각해 볼 것?

Python으로 시간초과하여 PyPy3으로 통과하였다. Python으로도 통과할 수 있는 방법이 있는지 공부해보아야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!