BOJ 11724 - 연결 요소의 갯수

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

DFS 를 이용해서 풀어야 하는 문제이다

연결 요소(Connected Component) 에 대한 위키백과의 정의를 보면 이렇게 서술하고 있다.

 

"In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph."

 

방향성이 없는 그래프 내에서 두개의 정점이 경로로 서로 연결되어 있는 서브 그래프를 연결요소로 부르는것 같다.

출처 : https://en.wikipedia.org/wiki/Component_(graph_theory)

 

정의에 따라 위 그림의 연결요소의 갯수는 3개이다.

 

- c++

#include <iostream>
#define MAX 1001
 
using namespace std;
 
int adj[MAX][MAX];
int checked[MAX];
int N, M, cnt;
 
void dfs(int x) {
    checked[x] = true;
    for (int i = 1; i <= N; i++) {
        if (!checked[i] && adj[x][i] == 1) {
            dfs(i);
        }
    }
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N >> M;
 
    int x, y;
    for (int i = 0; i < M; i++) {
        cin >> x >> y;
        adj[x][y] = 1;
        adj[y][x] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        if (!checked[i]) {
            dfs(i);
            cnt++;
        }
    }
 
    cout << cnt;
 
    return 0;
}

 

 

 

 

이전에 풀었었던, BOJ 2667 단지번호 붙이기 문제가 이 문제를 푸는데 있어서 힌트가 되었다.

sdy-study.tistory.com/51

BOJ 2667 - 단지번호 붙이기

 

DFS 함수 내에서 카운팅하는 것은 한 집단군내에 소속된 원소의 갯수를 구하는 것이고,

메인 함수 내에서 DFS 함수 수행이후에 카운팅을 하는 것은 집단군에 대한 갯수를 구하는것

이라는 개념을 근거로 풀어서 도움이 되었다.

 

추가적으로 노드 번호별로 방문 여부를 체크하는 것은, 

나동빈님의 DFS 강의에서 힌트를 얻을 수 있었다.

blog.naver.com/ndb796/221230945092

16. 깊이 우선 탐색(DFS)

 

 

정리를 해보면

이차원 배열로 입력값이 주어지고, 그 안에서 상하좌우 움직이면서 탐색하는 방식이면

이차원 배열과, dx, dy 배열을 생성해서 탐색을 돌리고,

위 문제처럼 각 노드 별로 탐색하는 방식이면, 각 노드가 연결되었음을 나타내기 위해

[x][y] 와 [y][x] 각각에 값을 부여한다.