[백준] 11724 : 연결 요소의 개수

연결 요소의 개수

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

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

---

연결 요소란 ?

문제를 본 후 연결 요소의 개념이 무엇인지 헷갈려 예제 입력을 직접 그래프를 그려보니 이해할 수 있었다.

1번의 경우 (1 - 2 - 5), (3 - 4 - 5)으로 두 개의 그래프로 이루어진 것을 볼 수 있다. 이는 연결 요소가 2개이다.

2번의 경우 (1 - 2 - 3 - 4 - 5 - 6)으로 하나의 그래프로 이루어진 것을 볼 수 있다. 이는 연결 요소가 1개이다.

즉, 이 문제에서 말하는 연결 요소는 그래프의 개수 혹은 영역의 개수이다.

---

코드 1 | DFS를 이용

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

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
cnt = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

for i in range(1, n+1):
    if not visited[i]:
        dfs(graph, visited, i)
        cnt += 1
else:
    print(cnt)

풀이 1

우선 문제를 보자마자 DFS를 이용한 풀이를 떠올렸다. for문을 이용해 정점의 개수만큼 돌면서 visited에 방문 기록을 하고 재귀가 끝나면 연결 요소 변수인 cnt += 1을 해주는 것이다.

---

코드 2 | BFS를 이용

import sys
from collections import deque

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

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
cnt = 0

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(graph, visited, i):
    q = deque([i])
    visited[i] = True
    while q:
        u = q.popleft()
        for j in graph[u]:
            if not visited[j]:
                q.append(j)
                visited[j] = True

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

풀이 2

BFS 또한 for문을 이용해 정점의 개수만큼 돌면서 방문 기록을 visited에 저장해주면서 해당 BFS 함수가 종료되었을 때 cnt += 1을 해준다.