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

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

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

이 문제 역시 같은 영역 색칠하기와 같은 문제 인것 같습니다.

이 문제를 풀 때 처음엔 BFS로 풀었습니다. 큐에 요소들을 집어넣고, 큐가 비워질 때 까지 탐색을 계속 하는 것이죠. 하지만 문제를 풀고 다른 사람들의 소스코드를 봤더니, DFS를 사용한 사람이 더 많았습니다. 

제가 생각한 이유는 '글쎄' 입니다. 두가지 방식이 있지만, 생각나는대로, 편한대로 풀면 되는 문제 같습니다. 

소스코드 :

1. BFS로 구현

// BFS로 구현 

#include 
#include 
#include 
using namespace std;


vector v[1001];
bool visited[1001] = { false, };
queue q;
void BFS(int idx) {
 q.push(idx);
 while (!q.empty()) {
  q.pop();
  for (int i = 0; i < v[idx].size(); i++) {
   if (visited[v[idx][i]] == false) {
    q.push(v[idx][i]);
    visited[v[idx][i]] = true;
   }
  }
  if (!q.empty()) {
   idx = q.front();
  }
 }

}

int main() {
 int N, M;
 cin >> N >> M; cin.ignore();
 for (int i = 0; i < M; i++) {
  int v1, v2;
  cin >> v1 >> v2; cin.ignore();
  v[v1].push_back(v2);
  v[v2].push_back(v1);
 }

 int color = 0;
 for (int i = 1; i <= N; i++) {
  if (!visited[i]) {
   visited[i] = true;
   BFS(i);
   color++;
  }
 }
 cout << color << endl;

}

2. DFS로 구현

#include 
#include 
using namespace std;


vector v[1001];
bool visited[1001] = { false, };

void DFS(int idx) {
    for(int i=0;i> N >> M; cin.ignore();
 for (int i = 0; i < M; i++) {
  int v1, v2;
  cin >> v1 >> v2; cin.ignore();
  v[v1].push_back(v2);
  v[v2].push_back(v1);
 }

 int color = 0;
 for (int i = 1; i <= N; i++) {
  if (!visited[i]) {
   visited[i] = true;
   DFS(i);
   color++;
  }
 }
 cout << color << endl;

}