[BaekJoon/백준] 11724번 C++

 

BFS 또는 DFS로 풀 수 있는 문제.

 

문제풀이를 한동안 안한 탓에.. BFS를 까먹어버려서 BFS 연습할 겸 풀었다.

 

벡터 배열을 사용했고, BFS답게 자료구조 queue와 visit 배열을 사용했다.

관련 해설은 이 블로그를 참고하면 좋다.

m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230944971&proxyReferer=https:%2F%2Fwww.google.com%2F

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int s, e;
vector<int> v[1001];
bool visit[1001];

queue<int> q;
int co = 0;

void bfs(int f) {
            
    q.push(f);
    visit[f] = true;
    
    while(!q.empty()) {
        int key = q.front();
        q.pop();
        
        // 벡터에서 숫자간 연결은 1부터지만, 실제 값일 들어있는 인덱스는 0부터임을 주의.
        for(int i = 0; i < v[key].size(); i++) {
            int x = v[key][i]; // v[key]와 연결되어있는것들 인덱스는 0, 1, 2 ...
            
            if(!visit[x]) {
                q.push(x);
                visit[x] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> M;
    
    for(int i = 0; i < M; i++) {
        cin >> s >> e;
        
        // 서로 연결표시
        v[s].push_back(e);
        v[e].push_back(s);
    }
    
    for(int i = 1; i <= N; i++) {
        if(visit[i])
            ;
        else {
            bfs(i);
            co++;
        }
        
    }
    
    
    cout << co;
    return 0;
}

queue에 push 하는 시점이 visit을 true 한다는 흐름을 잘 이해하자.

 

 

문제 해설 참고 추천

https://jdselectron.tistory.com/49