백준 11724 | DFS / BFS | 연결 요소의 개수 [파이썬 python]

11724번: 연결 요소의 개수

 

문제에서 연결 요소의 개수를 구하라고 했지만, 연결 요소의 뜻을 몰라서 헤매고 있었다.

하지만 주어진 예제 입력을 직접 손으로 그려보니 연결 요소가 무엇인지 알 수 있었다!

 

1번 예제 같은 경우는 직접 그래프를 그려보면 다음과 같은 모양으로 그려진다.

125 / 34 형태로, 2개의 그래프이자 2개의 영역으로 나눠진 것으로 볼 수 있다.

 

2번 예제 같은 경우는 직접 그래프를 그려보면 다음과 같은 모양으로 그려진다.

123456이 모두 연결되어 1개의 그래프이자 1개의 영역으로 볼 수 있다.

 

이를 통해 문제에서 말하는 연결 요소라는 것은 그래프의 개수 또는 영역의 개수로 이해하면 된다.

 

따라서, DFS 또는 BFS를 수행하는 횟수가 연결 요소의 개수이다. 

1번 예시는 2번의 DFS/BFS를 통해 125 방문, 34 방문을 할 수 있고, 2번 예시는 1번의 DFS/BFS를 통해 123456을 모두 방문할 수 있다.

DFS/BFS가 한 번 끝날 때마다 count+1을 해주면 최종적으로 연결요소의 개수를 구할 수 있다.

 

코드 - DFS 이용

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# dfs 함수
def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

n, m = map(int, input().split()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, i, visited)
        count += 1 # dfs 한 번 끝날 때마다 count+1

print(count)

 

1번부터 n번 노드를 순차적으로 방문하는 과정이 마지막 for문에 나타나 있다.

i=1일 때, 1번 노드를 방문하지 않았으면(visited[i] = False) dfs를 수행한다.

이때 dfs는 1번 노드와 연결된 노드를 모두 방문한다.

dfs가 끝나면 count+1을 해주고 다음 노드의 방문 여부를 확인한다.

 

만약 2번 노드가 1번 노드가 수행했던 dfs에 의해 visited[2]=True이면 dfs를 수행하지 않는다.

연쇄적으로 연결되어 있던 노드들은 모두 visited[i]=True일 것이다. 

하지만, 예시 1번처럼 모든 노드가 연결되어 있지 않아, i번 노드가 visited[i]=False이면 새로운 dfs를 수행할 것이고 i번 노드와 연결된 모든 노드들을 방문할 것이다. 

이런 식으로 dfs가 한 번 끝날 때마다 count+1을 하면 연결 노드의 개수를 구할 수 있다.

bfs도 진행 과정은 모두 같다.

 

코드 - BFS 이용

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# bfs 함수
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = 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()) # 정점의 개수, 간선의 개수
graph = [[] for _ in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

count = 0 # 연결 노드의 수
visited = [False] * (n+1)
for i in range(1, n+1):
    if not visited[i]:
        bfs(graph, i, visited) # bfs 한 번 끝날 때마다 count+1
        count += 1

print(count)

 

아래 사이트에서 코드를 실행시켜 보면 진행 과정을 시각적으로 확인할 수 있다.

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java