11724

백준 11724번

Link: 11724번: 연결 요소의 개수

---

문제 설명

기초적인 DFS, BFS 문제다.

2차원 배열에 연경 요소들을 1로 표시하고, BFS나 DFS를 사용하여 탐색하면서 연결된 요소의 갯수를 구하는 문제.

한가지 간과하기 쉬운 사실은, 이 그래프는 방향이 없는 그래프이기 때문에 연결시 쌍방향을 전부 1로 설정해줘야 한다는 점.

처음에는 배열 인덱스때문에 두어번 틀렸다가 맞게 풀었더니 시간초과가 났다.

BFS를 사용하여 시간 내에 풀기 위해서는 큐에서 정점을 뺄 때가 아닌 큐에 넣는 시점에 visit을 표시해야 한다는 것을 알게 되었다.

오늘은 BFS, DFS 감찾는다고 생각하고 앞으로 집중적으로 어려운 문제도 풀어볼 예정이다.

---

정답 코드

//
// Created by Keith_Lee on 21/01/2019.
//

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int map[1001][1001] = {0, };
bool visit[1001] = {false, };

int result = 0;

void BFS(int start){
    queue<int> Queue;
    Queue.push(start);

    while(!Queue.empty()){
        int next = Queue.front();
        Queue.pop();

        for(int i=1; i<=N; i++){
            if(!visit[i] && map[next][i] == 1){
                visit[i] = true;
                Queue.push(i);
            }
        }
    }

    result++;
}

int main(){
    cin >> N >> M;

    for(int i=0; i<M; i++){
        int start, end;
        cin >> start >> end;
        map[start][end] = 1;
        map[end][start] = 1;
    }

    for(int i=1; i<=N; i++){
        if(!visit[i]){
            visit[i] = true;
            BFS(i);
        }
    }

    cout << result << '\n';

    return 0;
}

---