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

문제

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

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

예제 입력 1 

6 5
1 2
2 5
5 1
3 4
4 6

예제 출력 1 

2

예제 입력 2 

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

---

나의 코드

[Python(파이썬)]

 

• 코드 1 - BFS사용

def bfs(x, check):
    queue = deque([x])
    check[x] = True     # x 노드 방문 표시
    while queue:    # 큐가 빌 때까지
        k = queue.popleft()
        for y in graph[k]:
            if not check[y]:    # x 노드와 연결된 방문하지 않은 원소들을 큐에 삽입
                queue.append(y)
                check[y] = True

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
cnt = 0

for _ in range(m):  # 인접리스트 생성
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

while False in visited:     # 방문하지 않은 노드가 없을때까지 반복
    cnt += 1	# 연결 요소 추가
    bfs(visited.index(False), visited)
print(cnt)

 

• 코드 2 - DFS 사용 

def dfs(x, check):
    check[x] = True     # x 노드 방문 표시
    for k in graph[x]:  # x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출
        if not check[k]:
            dfs(k, check)

import sys
sys.setrecursionlimit(10**6)	# 런타임 에러 - Recursion Error 방지하기 위함
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [True]+[False]*n
cnt = 0

for _ in range(m):  # 인접리스트 생성
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

while False in visited:     # 방문하지 않은 노드가 없을때까지 반복
    cnt += 1	# 연결 요소 추가
    dfs(visited.index(False), visited)
print(cnt)

 

---

코드 풀이

방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제이다. 

 

연결 요소(Connected Component)란?

무방향 그래프에서 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프

 

 

연결 요소의 개수 1

 

연결 요소의 개수 2

 

 

이 문제는 모든 정점을 방문하는 문제이기 때문에 DFS, BFS 둘 다 사용하여 탐색할 수 있다. 

 

예제 1번으로 생각해보자 (연결 요소 2개)

1) visited = [True]+[False]*6 -> 정점 방문 체크하는 리스트
2) 정점 1번으로 시작하여 연결된 모든 정점을 방문한다. 
3) visited = [True, True, True, False, False, True, False] 이 된다. 
4) visited에 False가 있는지 검사 -> index 3번이 False
5) 아직 방문하지 않은 정점 3번과 연결된 정점을 방문한다. 
6) visited = [True, True, True, True, True, True, True] 
7) visited에 False가 있는지 검사 -> 방문하지 않은 정점이 없으므로 종료

 

1-7번 순서를 아래 코드와 같이 구현할 수 있다. 

while False in visited:     # 방문하지 않은 노드가 없을때까지 반복
    cnt += 1	# 연결 요소 추가
    bfs(visited.index(False), visited)	
print(cnt)

 

• DFS, BFS 구현은 아래 두 게시물에 설명되어있다. 

[Algorithm] BFS, DFS (tistory.com)

[Algorithm] BFS, DFS

[백준(Baekjoon)] 1260 DFS와 BFS (tistory.com)

[백준(Baekjoon)] 1260 DFS와 BFS

---

※ DFS RecursionError 해결 방법

첫 번째 : DFS 구현 시 재귀를 사용하지 않기
두 번째 : sys.setrecursionlimit() 사용하기
세 번째 : DFS 대신 BFS로 구현하기

처음 문제를 풀 때 코드를 다음과 같이 DFS로 구현했다. 

def dfs(x, check):
    check[x] = True     # x 노드 방문 표시
    for k in graph[x]:  # x 노드와 연결된 아직 방문하지 않은 노드를 재귀호출
        if not check[k]:
            dfs(k, check)

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [True]+[False]*n
cnt = 0

for _ in range(m):  # 인접리스트 생성
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

while False in visited:     # 방문하지 않은 노드가 없을때까지 반복
    cnt += 1
    dfs(visited.index(False), visited)
print(cnt)

 

그 결과 아래 사진과 같이 런타임 에러가 발생한 것

RecursionError는 재귀와 관련된 에러이다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때인데 BOJ의 채점 서버에서 이 값은 1,000으로 되어 있다. 

 

따라서 RecursionERROR를 해결하기 위한 방법으로 

 

첫 번째 : DFS 구현 시 재귀를 사용하지 않기

DFS는 재귀 또는 스택을 사용하여 구현할 수 있기 때문에 재귀를 사용하지 않고 스택을 사용할 수 있다. 

 

두 번째 : sys.setrecursionlimit() 사용하기

이 함수를 사용하여 Python이 정한 최대 재귀 깊이를 변경할 수 있다. 최대 재귀 깊이를 1,000,000 정도로 크게 설정하면 런타임 에러 없이 실행된다. ( 재귀의 깊이가 채점 서버가 감당할 수 없는 정도로 깊어진다면,  Segmentation fault가 발생해 런타임 에러 이유로 SegFault를 받게 된다.)

import sys
sys.setrecursionlimit(10**6) # 런타임 에러 - Recursion Error 방지하기 위함

 

세 번째 : DFS 대신 BFS로 구현하기

이 문제는 모든 정점을 방문하는 문제이기 때문에 DFS, BFS 둘 다 사용하여 코드를 구현할 수 있다.

따라서 재귀를 사용한 DFS 대신 코드 1번과 같이 BFS로 구현할 수 있다. 

 

 

런타임 에러 (RecursionError) (acmicpc.net)

런타임 에러 (RecursionError)

 

런타임 에러(RecursionError)

런타임 에러

 

 

 

---

문제 출처

11724번: 연결 요소의 개수