백준 11724번: 연결 요소의 개수

백준 11724번: 연결 요소의 개수

아이디어

이미 방문한 노드를 dfs, bfs 함수의 인자로 집어넣으면 False를 반환하고, 방문하지 않은 노드를 함수의 인자로 집어넣으면 True를 반환하게 하였다. 이중 True를 반환하는 경우의 수를 모두 더하면 연결 요소의 개수이다.

코드(DFS)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [True] + [False]*N
connectedComponentCount = 0


def dfs(vertex):
    if visited[vertex]:
        return False
    visited[vertex] = True
    for i in graph[vertex]:
        if not visited[i]:
            dfs(i)
    return True


for i in range(M):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)
for i in graph:
    i.sort()

for i in range(1, N + 1):
    if dfs(i):
        connectedComponentCount += 1

print(connectedComponentCount)

코드(BFS)

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [True] + [False]*N
connectedComponentCount = 0
dq = deque()


def bfs(vertex):
    if visited[vertex]:
        return False
    visited[vertex] = True
    dq.append(vertex)
    while dq:
        v = dq.popleft()
        for i in graph[v]:
            if not visited[i]:
                dq.append(i)
                visited[i] = True
    return True


for i in range(M):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)
for i in graph:
    i.sort()

for i in range(1, N + 1):
    if bfs(i):
        connectedComponentCount += 1

print(connectedComponentCount)

여담

백준 채점 서버에서 파이썬 재귀 최대 깊이는 1,000이다. 재귀 깊이 제한을 풀어서 DFS로도 동작하게 만들었다.