[BOJ] 11724. 연결 요소의 개수(DFS, BFS)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제도 DFS 혹은 BFS 의 개념을 알고 구현할 수 있다면 충분히 풀 수 있는 문제다.

쉬운 문제지만 차근차근 풀어보면서 기본을 더 단단하게 해야지.

#. BFS Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <cstdio> #include <vector> #include <queue> using namespace std;   int main(void) {     int n, m, i, j, a, b, res = 0;     //freopen("input.txt", "rt", stdin);     scanf("%d %d", &n, &m);       vector<vector<int> > vt(n + 1);     vector<int> ck(n + 1);     queue<int> q;       for (i = 0; i < m; i++) {         scanf("%d %d", &a, &b);         vt[a].push_back(b);         vt[b].push_back(a);     }       for (i = 1; i <= n; i++) {         if (ck[i]) continue;           q.push(i);         while (!q.empty()) {             int x = q.front();             q.pop();               for (j = 0; j < vt[x].size(); j++) {                 if (!ck[vt[x][j]]) {                     ck[vt[x][j]] = 1;                     q.push(vt[x][j]);                 }             }         }           res++;     }       printf("%d\n", res);       return 0; } Colored by Color Scripter

cs

line 22~39) 모든 정점을 확인

line 23) 해당 정점이 방문한 정점이라면 continue;

line 25~36) 방문하지 않은 정점이라면 bfs 수행

line 38) 연결된 정점들을 모두 돌았으면 cnt

#. DFS Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <cstdio> #include <vector> using namespace std;   int ck[1001]; vector<int> vt[1001];   void dfs(int x)  {     ck[x] = 1;     for (int i = 0; i < vt[x].size(); i++) {         if (!ck[vt[x][i]])              dfs(vt[x][i]);     }   }   int main(void) {     int n, m, i, a, b, res = 0;     // freopen("input.txt", "rt", stdin);     scanf("%d %d", &n, &m);       for (i = 0; i < m; i++) {         scanf("%d %d", &a, &b);         vt[a].push_back(b);         vt[b].push_back(a);     }       for (i = 1; i <= n; i++) {         if (ck[i]) continue;         dfs(i);         res++;     }       printf("%d\n", res);       return 0; } Colored by Color Scripter

cs

line 30~34) 마찬가지로 모든 정점을 확인

line 31) 해당 정점이 방문한 정점이라면 continue;

line 32) 방문하지 않은 정점이라면 dfs 수행

line 33) 연결된 정점들을 모두 돌았으면 cnt