백준 [4803 트리] 파이썬 풀이

📌 문제 탐색하기

• 입력으로 여러 개의 테스트 케이스가 주어지며 각각의 테스트 케이스에서는 노드와 간선의 갯수, 간선의 구성 노드들이 주어진다.
• 해당 테스트 케이스에서 트리가 몇 개 존재하는지 판단하는 문제이다.
• 트리는 사이클이 존재하지 않는 그래프이기 때문에 사이클의 유무 판단이 중요할 것이다.

💡 알고리즘 선택

• 부모와 자식을 구분할 수 없는 간선이 입력으로 주어지므로 간선 정보를 양방향으로 저장할 필요가 있다.
• 그 후 BFS를 사용하여 queue를 탐색하는 과정에서 이미 방문했던 노드를 발견하는지 찾아서 사이클을 확인할 수 있다.
• 기존 BFS에서는 queue에 값을 추가하면서 방문 표시도 같이 해줬지만, 위와 같은 경우에선 queue에서 값을 뽑으면서 방문 표시를 해줘야한다. 그래야 트리 구조를 그리면서 마지막에 추가된 노드가 사이클을 구성하는지 발견할 수 있다.

📌 코드 설계하기

1. 문제의 input을 받음.

2. 간선 정보를 양방향으로 저장하기 위해 graph[a].append(b), graph[b].append(a)를 하여 노드들 간에 연결을 확인한다.

3. BFS를 구현하되, queue에서 값을 뽑으면서 방문 처리를 하도록 세부 설계를 바꿔준다.

4. 모든 노드 각각을 시작점으로 하여금 BFS를 하여 연결이 없는 노드가 하나인 트리의 갯수도 세어준다.

5. 각각의 테스트 케이스에서 caseNumber와 count(트리 갯수)를 조건에 맞게끔 출력한다.

 

📌 시도 회차 수정 사항 (Optional)

1회차에 성공

 

📌 정답 코드

from collections import deque
import sys

def BFS(start):
    answer = True
    queue = deque([start])
    while queue:
        v = queue.popleft()
        if visited[v] == 1:
            answer = False
        visited[v] = 1
        
        for i in graph[v]:
            if visited[i] == 0:
                queue.append(i)
    return answer

caseNumber = 0

while(True):
    caseNumber += 1
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    visited = [0] * (n+1)
    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)
        
    count = 0
    for i in range(1, n+1):
        if visited[i] == 1:
            continue
        if BFS(i) is True:
            count += 1
    
    if count == 0:
        print(f"Case {caseNumber}: No trees.")
    elif count == 1:
        print(f"Case {caseNumber}: There is one tree.")
    else:
        print(f"Case {caseNumber}: A forest of {count} trees.")