C++ 공부 21일차 (11047, 11279, 11724)

1주일 간의 휴가를 끝내고 다시 공부 모드로 돌입해야겠다

오늘 공부한 백준 (11047, 11279, 11724)

 

11724 연결요소의 개수

DFS, BFS를 제대로 구현할 줄 알면 간단한 문제이다

문제는 내가 제대로 할 줄을 모르는 것이다.

두고두고 잘 봐야하는 기본 문제이다.

#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 1001;
bool map[MAXN][MAXN] = {0, };
bool vst[MAXN];
int n, m;
int cnt = 0;

void dfs(int num) {
    vst[num] = true;
    for(int i = 1; i <= n; i++) {
        if(map[num][i] && !vst[i])
            dfs(i);
    }
}
int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        map[a][b] = true;
        map[b][a] = true;
    }
    for(int i = 1; i <= n; i++) {
        if(!vst[i]) {
            cnt++;
            dfs(i);
        }
    }
    cout << cnt;
} 

void bfs(int num){
    queue<int> q;
    q.push(num);
    vst[num] = true;
    
    while(!q.empty()){
        int curr = q.front();
        q.pop();
        
        for(int i=0; i<map[curr].size(); i++){
            int nxt = map[curr][i];
            
            if(!vst[nxt]){
                q.push(nxt);
                vst[nxt] = true;
            }
        }
    }
}