백준 11724: 연결 요소의 개수

 

📃 문제: 백준 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) 같은 간선은 한 번만 주어진다.

 

 

🥈 난이도: 실버 2

 

 

😲 사용한 개념: DFS(깊이우선탐색), 인접리스트

 

    ☝️ DFS란?

1️⃣ 탐색 시작 노드 정보를 스택에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ 스택 내 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드 정보를 스택에 삽입하고

pop연산과 동시에 방문 처리한다.
만일 방문하지 않은 인접 노드가 없다면 스택 내 최상단 노드를 꺼낸다.(빈 스택 상태)
3️⃣ 아직 방문처리되지 않은 수 중 가장 작은 수를 push하여, 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

    ✌️ 인접리스트란?

그래프의 각 노드에 인접한 노드들을 연결리스트로 표현하는 방법이다.
노드의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 해당 노드와 인접한 노드 정보가 저장된다.

문제에서 사용되는 무향 그래프의 경우, 위 그림의 그래프를 예시로 설명한다면 아래와 같이 표현될 것이다.

A[1]={2} //노드 1에 인접한 노드 : 2

A[2]={3, 4} //노드 2에 인접한 노드 : 3, 4

A[3]={2, 5} //노드 1에 인접한 노드 : 2, 5

A[4]={2} //노드 1에 인접한 노드 : 2

A[5]={3} //노드 1에 인접한 노드 : 3

 

 

 

 

📖 풀이 사고 과정

 

 

 

👩‍💻 구현 코드(c++ 사용)

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

void DFS(int i, vector<int> &visited, vector<vector<int>> &A);

int main(void) {
    int N, M, start, end,count=0;
    cin >> N >> M;
    vector<vector<int>> A(N);
    vector<int> visited(N, false);
    //인접리스트로 그래프 입력받기
    for (int i = 0; i < M; i++) {
        cin >> start >> end;
        A[start].push_back(end);
        A[end].push_back(start);
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            count++;
            DFS(i, visited, A);
        }
    }
    cout << count << endl;
    return 0;
}

void DFS(int i, vector<int>& visited, vector<vector<int>>& A) {
    if (visited[i]) return;
    
    visited[i] = true;
    for (int num : A[i]) {
        if (!visited[num]) {
            DFS(num, visited, A);
        }
      
    }
    
}