[백준] 연결 요소의 개수(python)

백준, 연결 요소의 개수

11724번: 연결 요소의 개수

TL;DR

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

문제 요약

1. 방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 프로그램을 작성하시오.

 

- 모든 노드 사이의 움직일 수 있는 무향, 양방향 그래프가 주어질 때, 연결 요소의 개수를 구하는 프로그렘을 작성해야 한다.

   (연결 요소에 대해서는 입출력 형태에서 확인한다.)

입출력 형태

입출력 예시

 

주어진 그래프를 그림으로 표현하면 아래 그림과 같이 표현할 수 있다.

 

그래프 표현

 

이 그래프는 두 개의 각각 연결 요소로 나눌 수 있다. 즉, 이 문제는 주어진 그래프에서 서로 연결된 그래프가 몇 개가 존재하는지를 계산해서 반환하는 문제가 되겠다. 리트코드의 문제 중 Numbers of Islands라는 문제와 매우 흡사하다. 이 문제에 대한 풀이는 여기서 확인할 수 있다.

풀이

이 문제는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 가지 방법으로 풀 수 있다.

첫 번째 방법은 DFS를 사용한 방법이다. 재귀적으로 구현했을 때, 한 가지 설정을 해줘야 한다. 백준에서는 recursion 제한이 걸려있기 때문에 이에 대한 설정을 바꾸는 구문이 하나 들어가야 한다.

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6) # 재귀 제한 해제

N, M = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visits = [False for _ in range(N + 1)]

def dfs(node):
    visits[node] = True

    for v in graph[node]:
        if not visits[v]:
            dfs(v)

answer = 0
for i in range(1, N + 1):
    if not visits[i]:
        dfs(i)
        answer += 1

print(answer)

 

DFS의 풀이 코드이다. 노드를 방문했는지 방문하지 않았는지 여부를 나누어 각 노드를 깊이 우선으로 탐색하며 방문, 방문한 노드는 True로 설정하여 방문했음을 표시한다. DFS가 수행되고 나면 방문 여부가 True로 변경되므로 하나의 연결 요소를 찾은 것이 된다. 다른 연결 요소가 존재한다면 노드가 False로 되어 있으므로 이에 대해 다시 DFS를 수행하고 개수를 추가하면 된다.

 

두 번째 방법은 BFS를 사용한 방법이다. 특이한 점이라면 deque를 사용했다는 것이다.

일반적인 queue 연산은 가장 앞에 요소를 반환하기 위해서는 pop(0)와 같은 형태로 사용해야 하고, 이는 시간 복잡도가 O(n)이 걸린다. 큰 차이는 없겠지만 큰 입력에 대해서는 효과적일 수 있으므로 O(1)의 시간복잡도로 0번째 요소를 pop할 수 있는 deque를 사용하였다.

import sys
from collections import defaultdict, deque

N, M = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visits = [False for _ in range(N + 1)]

def bfs(node):
    queue = deque([node])
    visits[node] = True

    while queue:
        visit = queue.popleft()
        
        for v in graph[visit]:
            if not visits[v]:
                visits[v] = True
                queue.append(v)

answer = 0
for i in range(1, N + 1):
    if not visits[i]:
        bfs(i)
        answer += 1

print(answer)

 

풀이 방법 자체는 DFS와 동일하다.