[알고리즘] 백준 11724 연결 요소(DFS)

안녕하세요, 감자코딩의 감자입니다. 

이번시간에 살펴볼 문제는 백준 알고리즘의 11724번 문제인데요. 이 문제는 그래프의 연결요소를 찾아보는 문제입니다.

♣ 1. 문제

연결 요소의 개수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	15569	7734	5108	47.318%

문제

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

입력

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

출력

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

예제 입력 1 

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

예제 출력 1 

2

예제 입력 2 

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

이번 문제는 바로, 그래프에 연결된 연결의 요소를 찾아내는 문제입니다. 과연 몇개의 간선(Edge)이 정점(Vertex)에 연결이 되어있는것일까요?

♣ 2. 문제 해결

1) 첫번째로 알아보셔야 할 조건은 정점의 개수와 간선의 개수 n,m을 입력을 받는것입니다. 하나의 정점에 몇개의 간선이 연결되어있는지를 알아보아야하는데요.

이때, 아! 하고 떠오르셨어야합니다.

바로 그래프 탐색 대표적인 탐색 방법인 DFS, BFS를 떠올리셔야합니다.

깊이 우선 탐색(DFS)

• Stack이용해서 갈 수 있는 만큼 최대 -> 갈수 없으면 이전 정점으로 돌아감.

넓이 우선 탐색(BFS)

• 큐를 이용 -> 갈 수 있는 정점 모두 Queue -> insert
• 중요 ! 먼저 넣고 -> Queue pop() ! 

이라고 생각하시면 되는데요.

각각의 그래프 탐색 방식이 다르기 때문에, 구현하는 방법도 너무나도 다릅니다.

보통 BFS를 사용하게 되면 Stack을 사용하거나 재귀호출을 이용한 구현을 하게 되며, DFS를 사용하게 된다면 Queue를 이용하는 방식이라고 알고 계셔야합니다.

2) 

저는 map이라는 인접리스트를 사용할 예정이구요. 

(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2 이라는 조건이 있으므로 각각의 vector형식의 배열에 1001이라는 값을 할당하였습니다. 또한, 내가 체크한 부분인지 아닌지를 확인하기 위한 check변수를 선언하여 문제를 해결 하였습니다.

결국, check된 부분이 false인 경우에 카운트 값을 하나씩 올려주면서 재귀호출을 하게 된다면 결국엔 그 정점(V)에 포함된 간선(E)의 연결요소의 개수를 알 수 있겠죠? 

그리고 시간복잡도에 대해서 말해보겠습니다.

시간복잡도는 현재 (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 의 조건을 가지고 있습니다.

N은 최대 1000까지의 수를 가질 수 있으며, M 같은경우는 (1000*(999-1)/2) 까지의 값을 가집니다.

약 500,000 정확히 말해서 499,500까지의 값을 가질 수 있다는 말인데요.

N의 시간복잡도에 대해서는 O(N^2)까지의 수를 계산 하였을때, 1000 * 1000 => 1,000,000 백만까지 나오게 됩니다. M같은경우는 O(M^2) 약 500,000 이기때문에 O(M^2)을 하게 되면 500,000 * 500,000 => 250,000,000,000 = 2500억정도의 시간복잡도가 계산 될 수 있기때문에 주의하여야합니다. 시간복잡도는 약 1초에 1억번 컴퓨터가 수행 할 수 있는 시간을 말하는데요.  2500억정도가 나오게된다면 컴퓨터 시간복잡도를 수행하는데 있어서 2500초 정도가 걸린다고 생각하시면 됩니다. 이러한 시간복잡도 또한 무시할 수 없는 알고리즘의 하나이기 때문에 주의를 귀울이셔야 할 것 같습니다. 

♣ 3. 소스코드

//

//  연결요소찾기(11724).cpp

//  beakjoon_algorithm

//

//  Created by kgh on 11/04/2019.

//  Copyright © 2019 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

#include <vector>

using namespace std;

vector<int> map[1001];

bool check[1001];

void dfs(int v){

    check[v] = true;

    for(int i=0; i<map[v].size(); i++){

        int next = map[v][i];

        if(check[next]==false){

            dfs(next);

        }

    }

}

int main(void){

    int n,m;

    cin >> n >> m;

    // 간선의 길이 만큼 정점 u, 정점 v

    for(int i=0; i< m; i++){

        int u,v;

        cin >> u >> v;

        map[u].push_back(v);

        map[v].push_back(u);

    }

    int cnt=0;

    for(int i=1; i<=n; i++){

        /*

         간선의 개수를 구하기 위해서는 dfs호출시에 check==false일경우 간선의 개수가 하나씩증가하는것을 알 수 있다

         단, dfs함수 안에서 if(check[next]==false) dfs(next);를 처리하면 값이 정확하게 반환이 안될 수 있음.

         */

        if(check[i] == false){

            dfs(i); //값 체크

            cnt++;

        }

    }

    cout << cnt;

}

저는 간단하게 DFS를 사용하여 문제를 풀이를 완료하였고, 가장 중요한 부분이라고 생각하는것은 

 if(check[i] == false){

            dfs(i); //값 체크

            cnt++;

        }

이 부분이였습니다. 체크 배열 변수로 방문하지 않은 곳이였을때 카운팅 값을 올려주면서 재귀호출을 진행한다면 결국 최종 갈수있는 정점까지의 탐색이 완료되고, 결국엔 cnt변수에 연결요소의 개수가 담길것입니다.