[DFS/BFS] 백준 11724. 연결 요소의 개수

11724번: 연결 요소의 개수

 

로직 구성:

우선 각 노드의 연결 관계가 무향이므로 간단한 그래프 문제라고 판단하였다.
또한 한번의 순회로 연결된 모든 노드를 방문, 그 이후 다른 노드에서 출발할 때 들르지 않은 노드가 있다는 건 별개로 연결된 그래프임을 이용하여 이를 count하였다.

 

특이점:

평소에는 sys.setrecursionlimit() 에 들어가는 값을 10**6 정도로 넉넉하게 설정해 왔다. 하지만 이와 같이 설정하면 메모리 초과가 발생하는 걸 확인할 수 있었다. 무엇이 문제인가 알아보다가 recursionlimit이 10**5 이하로 설정되면 정상적으로 통과하는 것을 확인할 수 있었다. recursionlimit의 설정 범위에 따라 메모리가 초과될 수도 있음을 항상 유념하자.

 

소스 코드:

DFS

import sys
sys.setrecursionlimit(10**4)

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

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1,N+1):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

 

BFS

from collections import deque as dq
def bfs(node):
    queue.append(node)
    visited[node] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

N, M = map(int, input().split())
queue = dq([])
visited = [False] * (N+1)
graph = [[] for _ in range(N+1)]
ans = 0

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        ans += 1
print(ans)