[백준] 11724번 연결 요소의 개수 파이썬 정답 코드

11724번: 연결 요소의 개수

---

1. 문제 내용

 

 

2. 접근 방식

• 너비 우선 탐색 방식으로 연결 요소 파악하기

처음에는 DFS (깊이 우선 탐색)으로 코드를 작성하여 제출하였지만, RecursionError가 나서 BFS로 바꾸었다.

 

• 집합을 사용하여 BFS에서 시간 줄이기

visited 리스트로 방문 여부를 체크하는 일반적인 코드는 아래 코드처럼 마지막에 모든 노드를 순회하면서 bfs 메서드를 호출하여야 했다.

result = 0
for e in range(1, n + 1):
    if not visited[e]:
        result += check_connected_component(e)
print(result)

따라서 bfs 메서드를 실행하기 위한 순회를 제거하고자 1 ~ n까지 노드를 담은 집합을 사용하였다. bfs 메서드 내에서 방문한 노드는 집합에서 삭제함으로써 방문 여부를 표현하였다.

 

 

3. 정답 코드

• sys.stdin.readline을 사용하여 입력 속도 개선 (일반 input 사용 시 시간 초과)

from collections import deque
import sys


input = sys.stdin.readline

def check_connected_component(x):
    queue = deque([x])

    while queue:
        node = queue.popleft()

        for z in graph[node]:
            if z in nodes:
                nodes.remove(z)
                queue.append(z)


def make_graph(r, c):
    data = [[] for _ in range(r + 1)]
    for _ in range(c):
        u, v = map(int, input().split())
        data[u].append(v)
        data[v].append(u)

    return data


n, m = map(int, input().split())
graph = make_graph(n, m)
nodes = {i for i in range(1, n + 1)}

result = 0
while nodes:
    check_connected_component(nodes.pop())
    result += 1
print(result)