연합

문제

풀이

그래프 문제였다. 그래프 내에서 연결된 집합이 몇개인지 찾으면 됐다. visit배열을 이용해서 방문한 배열을 체크할 수 있었다.

dfs보다는 bfs가 조금 더 눈에 보이는 느낌이라서 코드를 보고도 금방 이해할 수 있었다. 그냥 visit배열에 걸리지 않고 bfs 함수로 들어간 횟수를 체크해주면 돼서 식은 간단했다.

이 문제를 끝으로 구름톤 챌린지가 끝났다. 시간이 없어서, 까먹어서 등등...의 이유로 제대로 풀어보지 않고 넘어갔던 문제를 다시 풀어보니까 기분이 좋다. 물론 내 힘으로 해결하지 못한 문제들도 있었다. 그런 문제들을 마주칠때면 가슴이 답답하고 이런것도 못 푸는 내 실력이 미워졌지만 앞으로 공부하다보면 스스로 해결할 수 있지 않을까 싶다.

지금 풀고있는 문제들도 처음에는 못 풀었던 문제들이니까!

이번 챌린지 계기로 코테연습도 열심히 하고 기본적인 cs들도 놓치지 않고 공부했으면 좋겠다. 42과제 하다보니 이전에 부족했었던 구현력이 조금 올라가서 기분 좋은데, 꾸준히 내가 쥐고있는 것들 열심히 해보자. 파이팅!

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 2001;
vector<int> v[MAX];
int temp[MAX][MAX], visited[MAX];

void BFS(int S) {
    queue<int> Q;
    Q.push(S);
    visited[S] = 1;
    while (!Q.empty()) {
        int cur = Q.front(); 
        Q.pop();
        for (int i; i<v[cur].size();i++) {
            if (visited[i]) continue;
            visited[i] = 1;
            Q.push(i);
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        temp[a][b] = 1;
    }

    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (temp[i][j] && temp[j][i]) {
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        ans++;
        BFS(i);
    }

    cout << ans << '\n';
    return 0;
}