[Baekjoon] 11724: 연결 요소의 개수 - (C3, S2) DFS

문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력
첫째 줄에 연결 요소의 개수를 출력한다.

11724번: 연결 요소의 개수

 

연결 성분의 개수, 즉 최대로 연결된 부분 그래프들을 찾는 문제이다. 다음과 같은 예제 입력에서, 

6 5
1 2
2 5
5 1
3 4
4 6

 

이를 그래프로 표현하면 다음과 같다. 

2개의 부분 그래프로 구성되는 것을 볼 수 있다. 

 

이 문제에서 조건은 처음 입력한 그래프가 변하지 않으므로, 인접행렬을 사용하도록 한다. 필요한 정보와 기능만 정의해보자.

class Graph
{
private:
    int n_;                       // number of vertex
    vector<vector<int>> adj_mat_; // adjacency matrix

public:
    Graph(int n);

    void setEdge(int row, int col);

    void dfsMat(vector<bool> &visited, int v);

    int findConnectedComponent(vector<bool> &visited);
};

n_은 정점의 개수를, adj_mat_은 vector로 구현한 인접 행렬이다. Graph는 인자로 n을 입력받아, n X n 크기의 인접행렬을 0으로 초기화한다. setEdge는 인접 행렬에 간선을 입력, dfsMat은 DFS 탐색 함수, findConnectedComponent는 연결 성분의 개수를 반환한다. 각 함수를 살펴보자.

 

Graph::Graph(int n) : n_(n)
{
    adj_mat_.resize(n);
    for (int i = 0; i < n; i++)
        adj_mat_[i].resize(n, 0);
};

n_은 member initializer(초기화 리스트)를 사용해 n으로 초기화한다. adj_mat_은 n X n 크기의 행렬이어야 하고, 0으로 초기화(간선 x)해야 하므로 resize함수를 이용한다. 

 

resize함수는 capaticy를 변경하고 size는 유지한다. 즉, 기존 데이터를 유지한 채로 크기를 조정한다. 그리고 새로운 요소는 초기값으로 채워진다.

 

void Graph::setEdge(int row, int col)
{
    adj_mat_[row][col] = 1;
    adj_mat_[col][row] = 1;
}

무방향 그래프이므로, (row, col)과 (col, row)모두 1로 설정한다. 

 

void Graph::dfsMat(vector<bool> &visited, int v)
{
    visited[v] = true;
    for (int w = 0; w < n_; w++)
        if (adj_mat_[v][w] && !visited[w])
            dfsMat(visited, w);
}

DFS 알고리즘을 수행한다. visited 벡터를 참조형으로 전달받음에 유의한다.

 

int Graph::findConnectedComponent(vector<bool> &visited)
{
    int count = 0;
    for (int i = 0; i < n_; i++)
        if (!visited[i])
        {
            count++;
            dfsMat(visited, i);
        }
    return count;
}

연결 성분의 개수를 반환한다. 방문하지 않은 정점이 있다면, count를 1 증가시키고 새로운 부분 그래프에 대해 DFS를 수행한다. 

 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    Graph graph(N);
    vector<bool> visited(N, false);

    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        graph.setEdge(u - 1, v - 1); // 0-base indexing
    }

    cout << graph.findConnectedComponent(visited);

    return 0;
}

N과 M을 입력받아 graph와 visited를 초기화한다. for문에서는 간선을 입력받는데, 문제의 조건에서 간선의 양 끝점 u, v는 1 ≤ u, v ≤ N, u ≠ v 이다. 따라서 setEdge 함수의 인자로 전달할 때는 1을 빼서 0-base로 인덱싱해준다. 

 

여담으로, 첫 번째 시도는 입출력 최적화 코드를 삽입하지 않았다(sync_with_stdio, cin.tie). 삽입한 두 번째 시도와 비교하면 확연하게 차이가 나는 것을 확인할 수 있다.