[백준/파이썬] 11724번: 연결 요소의 개수

문제

https://www.acmicpc.net/problem/11724

풀이

• 정점의 개수와 간선의 개수가 주어짐
• 연결 요소의 개수 출력

그래프 탐색 문제
이 문제는 DFS와 BFS로 풀 수 있습니다.
기본적인 그래프 문제를 풀고 나서 풀면 좋은 문제입니다.
1260번: DFS와 BFS 이 문제를 풀고 푸시면 수월하게 풀 수 있습니다.

복습을 위해 DFS와 BFS 모두 사용하여 문제를 풀어보겠습니다.
깊이 우선 탐색부터 진행해볼게요

def dfs(v):
    visited[v] = 1 # 방문 표시
    for i in range(1, n+1): # 1번부터 n번 노드 검사
        if graph[v][i] == 1 and visited[i] == 0: # 연결된 노드 && 방문하지 않은 노드
            dfs(i)

여기까진 1260번과 동일하게 작성해줍니다.

그런데 여기서 연결 요소의 개수를 어떻게 출력할까요?
저는 처음에 DFS 함수 내에 cnt를 선언해서 그 값을 리턴 받으려고 했는데 생각보다 잘 안 되더군요 😢
그래서 이 방법은 빠르게 포기하고 다른 방법을 생각했어요 🤔

visited 배열을 이용했습니다.

cnt = 0  # 연결 요소 개수
for i in range(1, n + 1):  # 1번 정점부터 n번 정점까지 검사
    if visited[i] == 0:
        dfs(i)
        cnt += 1  # 탐색이 시작될 때마다 연결 요소 개수 증가

1. visited 배열에서 방문하지 않은 노드일 때 DFS를 수행
2. 탐색이 시작 될 때 count
3. 하나의 연결 요소에 속하는 모든 노드를 방문처리

이렇게 하면 연결 요소의 개수를 구할 수 있습니다.
그러나 여기까지만 작성하게 되면 런타임 에러가 발생합니다 🥲
왜 발생하는지 지피티에게 물어보니 재귀 깊이 제한 초과 때문이라고 하더군요

문제에서 N은 1000개, M은 10000개까지 가능하므로 깊이 우선 탐색이 너무 깊어지면 Python의 기본 재귀 한계를 초과할 수 있다고 합니다.

이를 해결하기 위해선 sys.setrecursionlimit()을 사용해서 재귀 한계를 늘려주면 됩니다.

import sys
sys.setrecursionlimit(10000)  # 재귀 한계 늘리기

---

다음은 BFS로 해볼게요
마찬가지로 기본적인 BFS 함수를 작성해줍니다.

def bfs(v):
    queue = deque([v]) # 시작 정점 큐에 추가
    visited[v] = 1 # 방문 처리

    while queue:
        node = queue.popleft() # 첫 요소 출력
        for i in range(1,n+1): # 모든 정점 검사
            if graph[node][i] == 1 and visited[i] == 0: # 연결된 노드 검사 && 방문하지 않은 노드
                queue.append(i) # 큐에 i값 추가
                visited[i] = 1 # 방문 처리

마찬가지로 연결 요소의 개수를 구할 때 동일한 방식을 이용하여 개수를 구할 수 있습니다.

cnt = 0  # 연결 요소 개수
for i in range(1, n + 1):  # 1번 정점부터 n번 정점까지 검사
    if visited[i] == 0:
        dfs(i)
        cnt += 1  # 탐색이 시작될 때마다 연결 요소 개수 증가

코드(DFS)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dfs(v):
    visited[v] = 1
    for i in range(1, n+1):
        if graph[v][i] == 1 and visited[i] == 0:
            dfs(i)

if __name__ == "__main__":
    n,m = map(int,input().split())
    graph = [[0] * (n+1) for _ in range(n+1)]
    visited = [0] * (n+1)

    for _ in range(m):
        a,b = map(int,input().split())
        graph[a][b] = graph[b][a] = 1
    
    cnt = 0
    for i in range(1,n+1):
        if visited[i] == 0:
            dfs(i)
            cnt += 1
    print(cnt)

코드(BFS)

from collections import deque
import sys
input = sys.stdin.readline

def bfs(v):
    queue = deque([v])
    visited[v] = 1

    while queue:
        node = queue.popleft()
        for i in range(1,n+1):
            if graph[node][i] == 1 and visited[i] == 0:
                queue.append(i)
                visited[i] = 1
    
if __name__ == "__main__":
    n,m = map(int,input().split())
    graph = [[0] * (n+1) for _ in range(n+1)]
    visited = [0] * (n+1)
    for _ in range(m):
        a,b = map(int,input().split())
        graph[a][b] = graph[b][a] = 1

    cnt = 0
    for i in range(1,n+1):
        if visited[i] == 0:
            bfs(i)
            cnt += 1
    print(cnt)