99. 백준 11724 번 C++ 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 백준 11724 번 연결 요소의 개수 입니다.

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

11724번: 연결 요소의 개수

 

먼저 백준 11724 번 연결 요소의 개수 C++ 정답 코드입니다. 설명은 아래에 있습니다.

#include <iostream>
#include <stack>
#define MAX 1001
using namespace std;
int N, M;
int graph[MAX][MAX] = {0,};
bool visited[MAX] = {false,};

void DFS(int i){
    stack<int> s;
    s.push(i);
    while (!s.empty()){
        int x = s.top(); s.pop();
        for (int n = 1; n <= N; n++){
            if (graph[x][n] == 1){
                if (!visited[n]){
                    visited[n] = true;
                    s.push(n);
                }
            }
        }
    }
}

int main(){
    int x, y, cnt = 0;
    cin >> N >> M;
    for (int i = 1; i <= M; i++){
        cin >> x >> y;
        graph[x][y] = 1;
        graph[y][x] = 1;
    }


    for (int i = 1; i <= N; i++){
        if (!visited[i]){
            DFS(i);
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}

 

문제 요약

 

숫자를 노드, -를 간선으로 하는 그래프 1-5-4, 2-3 가 있습니다.

이 그래프는 1,4,5끼리. 2,3 끼리 연결 되어 있습니다.

이렇게 간선으로 연결된 노드들의 집합을 연결 요소라고 하고, 방금 예시를 든 그래프의 연결 요소의 개수는 2개입니다.

노드와 간선을 입력 받고 해당 그래프의 연결요소를 출력하는 문제입니다.

 

문제 접근

DFS, 혹은 BFS를 이용하여

1. 아직 한번도 방문하지 않고

2. 두 노드가 간선으로 연결된 경우에만 방문합니다.

위의 2가지 방법으로 모든 노드를 DFS, BFS를 통해 방문을 하게 되면

1. 한번도 방문하지 않은 연결 요소의 노드일 경우 나머지 모든 노드는 방문처리하게 됩니다.

2. 방문 했던 연결 요소의 노드일 경우 방문하지 못합니다.

 

따라서 연결 요소의 개수 만큼만 DFS, BFS가 동작하게 됩니다.

우리는 DFS, BFS 동작 횟수만 카운트 해주면 됩니다.

  

 

C++ 코드 구현

 

노드와 간선의 개수, 그래프, 노드를 방문했는지 확인할 행렬 visitied 까지 선언하고 입력받습니다. 

int N, M;
int graph[MAX][MAX] = {0,};
bool visited[MAX] = {false,};

for (int i = 1; i <= M; i++){
    cin >> x >> y;
    graph[x][y] = 1;
    graph[y][x] = 1;
}

 

연결된 요소들을 하나씩 방문하는 방법중 하나인 DFS를 구현했습니다. (stack으로 구현)

void DFS(int i){
    stack<int> s;
    s.push(i);
    while (!s.empty()){
        int x = s.top(); s.pop();
        for (int n = 1; n <= N; n++){
            if (graph[x][n] == 1){
                if (!visited[n]){
                    visited[n] = true;
                    s.push(n);
                }
            }
        }
    }
}

 간선으로 연결된 노드 중 방문하지 않은 곳이 있다면 방문하는 방식입니다.

 

이제 모든 노드들을 탐색하면서 DFS가 동작한 횟수를 count 해주고 출력하면 됩니다.

for (int i = 1; i <= N; i++){
    if (!visited[i]){
        DFS(i);
        cnt++;
    }
}

cout << cnt;

 

백준 11724 번 연결 요소의 개수 C++ 최종 코드입니다.

#include <iostream>
#include <stack>
#define MAX 1001
using namespace std;
int N, M;
int graph[MAX][MAX] = {0,};
bool visited[MAX] = {false,};

void DFS(int i){
    stack<int> s;
    s.push(i);
    while (!s.empty()){
        int x = s.top(); s.pop();
        for (int n = 1; n <= N; n++){
            if (graph[x][n] == 1){
                if (!visited[n]){
                    visited[n] = true;
                    s.push(n);
                }
            }
        }
    }
}

int main(){
    int x, y, cnt = 0;
    cin >> N >> M;
    for (int i = 1; i <= M; i++){
        cin >> x >> y;
        graph[x][y] = 1;
        graph[y][x] = 1;
    }


    for (int i = 1; i <= N; i++){
        if (!visited[i]){
            DFS(i);
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}

 

백준 11724 번 연결 요소의 개수 자세한 설명 및 C++ 코드였습니다.

감사합니다.