[백준 리뷰] 11724 연결 요소의 개수

문제번호: 11724

사용 언어: C++

문제 링크: https://www.acmicpc.net/problem/11724

전체 코드 보기

#include <iostream>
#include <vector>

using namespace std;

#define WHITE 1
#define GRAY 2
#define BLACK 0

void DFS(vector<vector<int> > *graph, vector<int> *check_node, int start)
{
    for(int i = 0 ; i < (*graph)[start].size() ; i++)
    {
        if((*check_node)[(*graph)[start][i]] == WHITE)
        {
            (*check_node)[(*graph)[start][i]] = GRAY;
            DFS(graph, check_node, (*graph)[start][i]);
            (*check_node)[(*graph)[start][i]] = BLACK;
        }
    }
}

int main()
{
    int n, m;
    int answer = 0;

    cin >> n >> m;

    vector<vector<int> > graph(n);
    vector<int> check_node(n, WHITE);

    // make given graph
    for(int i = 0 ; i < m ; i++)
    {
        int u, v;

        cin >> u >> v;

        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

    for(int i = 0 ; i < n ; i++)
    {
        if(check_node[i] == WHITE)
        {
            answer++;

            check_node[i] = GRAY;
            DFS(&graph, &check_node, i);
            check_node[i] = BLACK;
        }
    }

    cout << answer << endl;

    return 0;
}

설명

이 문제는 먼저, DFS/BFS를 이용하여 풀어내는 것이 핵심입니다. 애초에 그래프의 Connected Component를 구하는 것이니까요.
Connected Component는 다음과 같습니다.

 

다음과 같은 상황에서, 우리는 "그래프가 3개 있다." 라고도 할 수 있지만, "1개의 그래프가 3부분으로 나누어져 있다." 라고도 할 수 있습니다. 이 때를 Connected Component, 즉 연결되어있는 요소가 총 3개 있다라고 말을 합니다.

---

BFS/DFS란?

BFS(Breadth-First Search)는 번역하면 "너비 우선 탐색"입니다. 랜덤한 node 하나를 정한 뒤, 해당 node를 중심으로 주변 노드들을 먼저 탐색하고, 그 다음 다시 탐색된 노드들 중 하나를 정하여 또 그 주변 노드들을 탐색하는 방식입니다. 정확한 순서는 다음과 같습니다.

1. Node 한개를 정한다.
2. 해당 Node와 인접한 Node들을 모두 탐색한다. 이 때, 탐색중인 Node들은 모두 Queue에 저장한다.
3. 모든 Node의 탐색이 끝나면, 탐색완료를 선언한다.
4. Queue에서 Node 하나를 꺼낸다.
5. Queue에 아무것도 남지 않을 때까지 2~4번을 반복한다.

DFS(Depth-First Search)는 번역하면 "깊이 우선 탐색"입니다. 이는 BFS와 반대로, 우선 한 방향으로 쭉 탐색하고 들어간 다음, 탐색이 끝나면 아직 탐색이 덜 된 다른 Node들을 방문하는 방식입니다. 정확한 순서는 다음과 같습니다.

1. Node 한개를 정한다.
2. 해당 Node와 인접한 Node(탐색되지 않은) 하나를 찾아 탐색한다. 이 때, 현위치를 Stack에 저장한다.
3. 인접한 탐색되지 않은 Node가 없을때까지 2번을 반복한다.
4. 탐색되지 않은 Node가 없을 때에는 Stack을 Pop한다. 탐색되지 않은 인접 Node가 있을때까지 반복한다.
5. Stack에 아무것도 남지 않을 때까지2~4를 반복한다.

둘의 차이점을 아시겠나요? 저는 이번 문제를 DFS를 이용하여 풀어보았습니다. 이유는.. 더 쉬워보여서 입니다..ㅎ

---

코드 설명은 다음과 같습니다.

우선, 탐색 여부를 확인할 수 있도록 색상을 지정합니다. 이는 반드시 색상일 필요는 없습니다.

#define WHITE 1  // 탐색되지 않음
#define GRAY 2   // 탐색중
#define BLACK 0  // 탐색 완료

그래프를 만들어 줍니다. 그래프를 만드는 방법에는 여러 가지가 있으나, 이번에는 vector 두개를 이용하여 만들도록 하겠습니다.

    vector<vector<int> > graph(n);
    vector<int> check_node(n, WHITE);

    // make given graph
    for(int i = 0 ; i < m ; i++)
    {
        int u, v;

        cin >> u >> v;

        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

첫 번째 vector인 graph는 Node에 대한 내용입니다. 어떤 Node에 어떤 Node가 연결되어있는지를 알 수 있습니다.
두 번째 vector인 check_node는 탐색 여부에 대한 설명입니다. 사실, 이는 graph vector과 합칠 수는 있으나, 더 복잡해질 것 같아서 그렇게 하지는 않았습니다.

다음과 같은 그래프가 있을 때, 값이 어떻게 들어가는지를 확인하며 위 벡터가 그래프를 만드는 방법을 알아보도록 합시다.
이 Graph는 다음과 같은 입력을 갖습니다.

1 2
3 4
6 2
5 6
1 6

이 때, graph 벡터는 다음과 같은 값을 가지게 됩니다.

graph[0] -> 1, 5
graph[1] -> 0, 5
graph[2] -> 3
graph[3] -> 2
graph[4] -> 5
graph[5] -> 0, 1, 4

그림에서 1부터 6까지 표현된 각 Node들은 벡터로 표현할 때 편하게 표현할 수 있도록 하기 위해서 0부터 5까지로 1씩 낮추었습니다.
check_node 벡터의 경우, 해당 Node의 탐색 여부를 확인하기 위한 벡터입니다.

이 부분이 DFS 부분입니다.

void DFS(vector<vector<int> > *graph, vector<int> *check_node, int start)
{
    for(int i = 0 ; i < (*graph)[start].size() ; i++)
    {
        if((*check_node)[(*graph)[start][i]] == WHITE)
        {
            (*check_node)[(*graph)[start][i]] = GRAY;
            DFS(graph, check_node, (*graph)[start][i]);
            (*check_node)[(*graph)[start][i]] = BLACK;
        }
    }
}

쓰여있는 내용이 조금 복잡해 보이지만 별 거 없습니다. graph와 check_node 벡터를 받아온 뒤, start 지점에서부터 탐색을 한다는 내용입니다.

for문을 통해 start node와 연결된 모든 지점을 탐색하도록 지정합니다. (*graph)[start].size()를 통해 연결된 모든 node들을 탐색합니다. 예를 들어, 위의 입력을 기준으로 start값이 1인 경우, 0, 5번 node를 탐색하게 됩니다.

그 다음, 해당 부분이 WHITE로, 탐색되지 않은 상태인 곳을 찾습니다. 이미 탐색중이거나 탐색이 완료된 node는 방문하지 않습니다.

탐색되지 않은 node를 발견하면, GRAY(탐색중)으로 해당 node를 변경하고, 다시 DFS를 통해 탐색을 시작합니다.

더 이상 탐색할 node가 없다면, 탐색 종료를 선언하고 해당 node를 BLACK(탐색완료)으로 바꾸어줍니다.

 

 

이제, 탐색을 할 수 있게 되었습니다. 그렇다면 Connected Component는 어떻게 확인할 수 있을까요?

새로운 탐색이 시작되면 Connected Component의 개수가 늘어나도록 프로그래밍하면 간단하게 해결할 수 있습니다. 해당 부분은 다음과 같습니다.

for(int i = 0 ; i < n ; i++)
{
    if(check_node[i] == WHITE)
    {
        answer++;

        check_node[i] = GRAY;
        DFS(&graph, &check_node, i);
        check_node[i] = BLACK;
    }
}

이는 main 함수 안에 있는 코드입니다. 위의 DFS 코드와 비슷해 보이죠?

우선 check_node가 아직 탐색되지 않은 node를 발견하면 answer을 1 증가시킵니다. answer은 connected comonent의 개수를 의미합니다.
이후, DFS의 메인 로직과 동일하게 진행됩니다. DFS의 로직 안에서는 answer를 증가시키지 않으므로, 해당 코드는 새롭게 탐색이 시작될 때에만 작동하게 됩니다.

---

주의할 점!!(메모리 초과 문제)

 

이 부분은 제가 겪었던 실수입니다. 모든 답은 정확하게 나오는데에, 메모리 초과가 발생해 정답 처리가 되지 않았었습니다.
제 코드를 잘 살펴보면 DFS 부분에서 graph와 check_node 를 모두 포인터로 전달하는 것을 알 수 있습니다.
check_node는 어차피 계속 수정을 해야 하는 부분이니 그렇다고 치지만, graph는 왜 굳이 포인터로 전달하는 방식을 취했을까요? 가독성을 잃어가면서 말입니다.

그 답은 바로 메모리 때문입니다. DFS 함수를 여러번 실행해야 하는 코드의 특성상, graph를 벡터로 전달하게 되면 전달할 때마다 새로운 벡터가 생성됩니다. 만약 벡터의 크기가 조금이라도 컸다면, 그리고 DFS를 많이 실행하게 된다면, 이는 곧 치명적인 메모리 문제로 이어지게 됩니다.

따라서 벡터 포인터로 해당 값을 전송하게 되었습니다. 포인터로 전송을 하기 때문에 주소값 하나 크기만 전송하면 되고, 벡터를 새로 생성할 필요가 없었기 때문에 메모리 문제에서 자유로울 수 있었습니다.
작은 단위의 테스트 케이스에서는 중요하지 않은 이슈이지만, 큰 규모의 프로그래밍을 하게 된다면 꼭 중요하게 보고 넘어가야 할 문제인 것 같습니다.