백준 6207번 Cow Picnic [C++]

https://www.acmicpc.net/problem/6207

 

#문제 번역

 

문제 설명

소들은 소풍을 가고 싶어 합니다! Farmer John의 K마리 소들은 각각 N개의 목초지 중 한 곳에서 풀을 뜯고 있습니다. 목초지는 1번부터 N번까지 번호가 매겨져 있으며, 일방통행 경로 M개로 연결되어 있습니다(경로는 자기 자신을 연결하는 경우는 없습니다).

소들은 동일한 목초지에서 만나 소풍을 가고 싶어 하지만, 일방통행 경로로 인해 어떤 소들은 특정 목초지로만 갈 수 있을 수도 있습니다. 모든 소들이 도달할 수 있는 목초지가 몇 개인지 찾아서 소들이 만날 수 있는 소풍 장소를 정해주세요.

입력

1번째 줄: 세 개의 정수 K, N, M이 공백으로 구분되어 주어집니다. (1 ≤ K ≤ 100, 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000)

2번째 줄부터 K개의 줄: 각 줄은 소들이 있는 목초지 번호가 하나씩 주어집니다. 이 목초지 번호는 1부터 N까지의 숫자입니다.

K+2번째 줄부터 M+K+1번째 줄: 각 줄에는 두 개의 정수 A와 B가 주어지며, 이는 목초지 A에서 목초지 B로 가는 일방통행 경로가 있음을 나타냅니다. (1 ≤ A, B ≤ N, A ≠ B)

출력

모든 소들이 일방통행 경로를 통해 도달할 수 있는 목초지의 수를 출력하세요.

 

 

#문제 간단 정리

그래프 탐색문제 

말 그대로 각 소들이 전부 방문하는 목초지의 개수를 찾아주면 된다

 

 

#문제 해결 방법

나는 각 소 들을 2차원 배열로

방문배열로 만들어줬고

방문여부는 dfs로 탐색하였다

 

그리고 각 목초지에 모든소가 방문하는지 탐색해주면 된다.

 

 

#전체 코드

 

#include <iostream>
#include <vector>

using namespace std;

int k, n, m;
vector<vector<int>> graph;
vector<int> cowPos;
vector<vector<bool>> check;

void dfs(int cowNum, int index) {
    for (auto a : graph[index]) {
        if (!check[cowNum][a]) {
            check[cowNum][a] = true;
            dfs(cowNum, a);
        }
    }
}

int main() {
    cin >> k >> n >> m;
    check.resize(k, vector<bool>(n, false));

    for (int i = 0; i < k; i++) {
        int input;
        cin >> input;
        cowPos.push_back(input - 1);
    }

    graph.resize(n);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a - 1].push_back(b - 1);
    }

    for (int i = 0; i < k; i++) {
        int cp = cowPos[i];
        check[i][cp] = true;
        dfs(i, cp);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        bool all_cows_can_reach = true;
        for (int j = 0; j < k; j++) {
            if (!check[j][i]) {
                all_cows_can_reach = false;
                break;
            }
        }
        if (all_cows_can_reach) ans++;
    }

    cout << ans << endl;

    return 0;
}