BOJ 11724 · 연결 요소의 개수

알고리즘 분류 : DFS  

DFS를 통해 연결 그래프의 개수를 확인하면 된다. 방문 여부를 저장하는 check 배열을 따로 만들고, N개의 노드 개수만큼 루프를 돌면서 방문하지 않은 곳에 DFS를 돌리면 된다. 처음 DFS를 호출할 때 카운트를 하면 연결 요소의 개수를 셀 수 있다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
using namespace std;

int n, m;
vector<int> a[1001];
bool check[1001];

void dfs(int now) {
    check[now] = true;
    for (int i=0; i<(int)a[now].size(); i++) {
        int next = a[now][i];
        if (!check[next]) {
            dfs(next);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int cnt = 0;
    for (int i=1; i<=n; i++) {
        if (!check[i]) {
            dfs(i);
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

---

Python 3 소스코드

import sys
sys.setrecursionlimit(10000)

n, m = map(int, sys.stdin.readline().split())
a = [[] for _ in range(n+1)]
check = [False]*(n+1)
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    a[u].append(v)
    a[v].append(u)

def dfs(now):
    check[now] = True
    for i in a[now]:
        if check[i] is False:
            dfs(i)

cnt = 0
for i in range(1, n+1):
    if check[i] is False:
        dfs(i)
        cnt += 1
print(cnt)

✓ Python을 통해 재귀 방식의 DFS로 짜면 재귀 제한에 걸려 런타임 에러(Runtime Error; RE)를 받게 된다.

✓ 스택으로 바꿔서 구현하거나, sys.setrecursionlimit를 통해 재귀 제한 범위를 늘리면 된다.

---

참고

• 백준 온라인 저지 : BOJ 11724