[백준] 21937번 : 작업 (C++)

21937번 : 작업

---

문제)

민상이는 자신이 해야할 작업 N개를 아래와 같이 작업 순서도로 그려보았다.

 

 

위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다.

작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다.

민상이는 오늘 반드시 끝낼 작업 X가 있다. 민상이가 작업 X 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자!

 

 

입력 :

민상이가 작업할 개수 N와 작업 순서 정보의 개수 M이 공백으로 구분되어 주어진다.

두 번째줄부터 M + 1 줄까지 작업 A_i와 작업 B_i가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작업 B_i를 하기 위해서 바로 이전에 작업 A_i를 먼저 해야한다는 의미이다. 중복된 정보는 주어지지 않는다.

마지막 줄에는 민상이가 오늘 반드시 끝내야하는 작업 X가 주어진다.

 

 

 

출력 :

민상이가 작업 X를 하기 위해 먼저 해야하는 일의 개수를 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
vector<bool> visited;
int cnt = -1;
 
void dfs(int cur)
{
    visited[cur] = 1;
    cnt++;
    for (auto nxt : vec[cur])
    {    // 이미 방문한 곳은 중복해서 방문하면 안된다.
        if (visited[nxt]) continue;
        dfs(nxt);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    vec.resize(n + 1, vector<int>());
    visited.resize(n + 1, 0);
    
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        // 방향을 역으로 생각하면 된다.
        vec[b].push_back(a);
    }
 
    int root = 0;
    cin >> root;
    
    dfs(root);
 
    cout << cnt;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/21937 

21937번: 작업