[백준(BOJ)] 11724번 연결 요소의 개수(DFS, BFS) C++

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

11724번: 연결 요소의 개수

 

 

어떤 문제인가?

그래프를 입력받고 연결 요소의 개수를 출력하면 된다.

이 문제를 풀기위해선 먼저 연결 요소가 무엇인지 알아야 한다.

간단하게 말하면 나누어진 각각의 그래프들을 연결 요소라고 한다.

 

문제의 첫 번째 예시대로 입력을 받으면

1-2-5,  3-4-6이 연결된 두 개의 연결 요소가 존재하는 것이다.

 

접근 방법

한 정점을 시작으로 그래프를 탐색한다.

그렇게 되면 그 정점과 연결된 정점들은 방문처리가 된다.

즉, 하나의 연결 요소를 이루는 정점들이라는 소리이다.

 

따라서, 한 정점으로 그래프 탐색을 끝난 후에도 어떠한 정점이 방문처리가 되어있지 않다는 것은

서로 다른 연결 요소에 속해 있다는 소리이다.

 

int n, m;
cin >> n >> m;

문제에서 주어진 변수를 선언하고 입력받는다.

 

while (m--) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
}

간선의 개수만큼 정점을 입력받는다.

 

int cnt = 0;

연결 요소의 개수를 저장할 변수이다.

 

for (int i = 1; i <= n; i++) {
    if (!visited[i]) {
        //bfs(i);
        dfs(i);
        cnt++;
    }
}

그리고 반복문을 통해 그래프 탐색을 할 것이다.

만약 i 번째 인덱스가 방문되지 않았다면 그래프 탐색을 진행한다.

 

이때, dfs, bfs 어떠한 방식으로 해도 상관없다.

if문의 조건을 통과하여 함수가 호출될 때마다 cnt를 증가시켜준다.

 

문제의 예시인 1-2-5, 3-4-6을 보자.

맨 처음엔 1이 방문되지 않았으므로 방문을 시작한다.

그러면 1,2,5가 방문처리되어있을 것이다.

 

반목 문을 돌다 3차례가 되었을 때 방문되지 않았으므로 방문을 시작한다.

그르면 3,4,6이 방문처리되었을 것이다.

 

각 경우마다 cnt를 증가시켜주어 연결 요소의 개수가 2개임을 알 수 있다.

 

cout << cnt;

cnt를 출력해주면 끝!!

 

 

무엇이 어려웠는가?

처음엔 연결요소의 개수를 어떻게 측정해야하나 잘 모르겠었다.

그래프 탐색과, 연결요소의 개념을 다시 천천히 생각해보니 금방 해답을 찾을 수 있었다.

 

 

배운 점

아무리 배웠던 내용이라도 기초와 복습이 중요하다.

내 뇌는 잘 까먹어서 주기적으로 상기를 시켜줘야한다ㅋㅋ