[c++][백준 21937][bfs] 작업 - 컴도리돌이

---

 

21937번: 작업

---

풀이 과정

 

해당 문제는 bfs,dfs로 풀어도 될 것같다. 나는 bfs가 친숙해서 해당 문제를 bfs를 풀었다. 입력 값 'process'라는 벡터는 이차원 배열로 구성하였고 해당 노드의 자식 노드를 삽입해줬다.

그 다음 문제에서 요구하는 x라는 입력 값을 받아서 해당 x에 대한 bfs 탐색을 한다. 그 다음부터는 평범한 bfs 코드이다. x 밑에 있는 자식 노드가 있고 해당 자식 노드를 방문하지 않았다면 큐에 삽입하여 해당 자식노드를 탐색.. 탐색 하는 방식으로 구현했다. 방문하지 않은 자식 노드를 탐색하기 전에 cnt라는 결과 값을 1씩 증가 시켰다. 그 다음에 탐색이 끝나고 반환 값을 출력 시켰다.

---

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

using namespace std;

int n,m,x;

vector<vector<int>> process;
vector<int> visited;
void input(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;

    process.resize(n+1,vector<int>());
    visited.resize(n+1, 0);
    for(int i=0,a,b; i<m; i++){
        cin >> a >> b;
        process[b].push_back(a);
    }
    cin >> x;
}

int bfs(){
    visited[x] = true;
    queue<int> q;
    q.push(x);

    int cnt =0;
    while(!q.empty()){

        int cur = q.front();
        q.pop();

        for(int i=0; i<process[cur].size(); i++){
            int next = process[cur][i];
            if(!visited[next]){
                cnt++;
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return cnt;
}

void solution(){

    input();
    cout << bfs();
}

int main(){
    solution();
    return 0;
}

---