[SWEA 7465][C++] 창용 마을 무리의 개수(D4)

[문제보기]

 7465. 창용 마을 무리의 개수

SW Expert Academy

 

[풀이과정]

  (1) dfs(int node)

       node라는 변수는 사람의 번호를 의미한다. 한번 검사한 사람은 false로 바꿔 다시 검사를 하지 않게 바꾼다.

       그리고 for문을 통해 그 사람이 아는 사람의 정보를 가져와 그 사람이 검사를 하지 않았으면 dfs()를 다음 사람에

       대해 실행해준다. 

 

 (2) main()

      vector를 통해 각 사람이 누구를 알고 있는지에 대한 정보를 저장한다. 이때 A라는 사람이 B라는 사람을 알면

      B라는 사람도 A라는 사람을 아는 것이기 때문에 무방향 그래프로 생각하여 각 번호에 대해 둘다 정보를

      입력해준다.

      for문을 돌릴건데 이때 check[] 배열 변수를 통해 이 사람에 대해 검사를 했는지 확인 후 검사를 하지 않았으면

      dfs를 실행 무리 숫자를 하나 늘려준다. 

[소스코드]

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> v;
bool check[101];
int n, m;

void dfs(int node){
    check[node] = false;
    for(int i=0; i<v[node].size(); i++){
        int next = v[node][i];
        if(check[next]){
            dfs(next);
        }
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    int T;
    cin >> T;
    for(int test = 1; test <= T; test++){
        cin >> n >> m;
        v = vector<vector<int>>(n+1, vector<int>());
        memset(check, true, sizeof(check));

        int x, y;
        for(int i=0; i<m; i++){
            cin >> x >> y;
            v[x].push_back(y);
            v[y].push_back(x);
        }

        int cnt = 0;
        for(int i=1; i<=n; i++){
            if(check[i]){
                cnt++;
                dfs(i);
            }
        }
        
        cout << "#" << test << " " << cnt << "\n";
    }
}

 

[해결과정 중 실수한 부분]