백준 2617 구슬 찾기

문제

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

풀이방법

처음에 아 이거 어떻게 풀지 이러다가 ... a라는 구슬은 b보다 무거울 수도 b라는 구슬보다 가벼울 수도 있다.. 이렇게 해서 indegree, outdegree를 생각하면서 있었는데..

제가 아는건 위상정렬을 queue로 푸는 것이었는데 흠.... 그러한 방식으로 가능할지 싶었는데 너무 몰라서 답안을 보게 되었습니다..

어렵게 생각한거 같다 특정노드보다 무거운 구슬들이 n / 2보다 많거나
특정노드보다 가벼운 구슬들이 n / 2보다 많으면 무조건 중간은 안된다 ..

이걸 보면 dfs를 두번 돌리면 되는것이다. 처음부터 백터를 두개로 놓고 각각의벡터들을 dfs로 돌리면 되는 문제였다

여기서 주의할점은 dfs처음 시작할때 res = 1로 설정해야한다 그렇다가 만약 하나도 해당이 안된다면 res -= 1로 계산을 해주어야한다

왜 1로 하나? 1로 하지않으면 체킹이 안되기때문이다.

소스

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> h[101];
vector<int> l[101];
bool hVisited[101];
bool lVisited[101];

//root노드가 젤 무겁  -> child 노드들은 자기보다 가벼운 것들 
int Hdsf(int n) {

    int res = 1;
    for (int i = 0; i < h[n].size(); i++)
    {
        if (!lVisited[h[n][i]]) {
            lVisited[h[n][i]] = true;
            res += Hdsf(h[n][i]);
        }
    }
    return res;
}

int Ldfs(int n) {

    int res = 1;
    for (int i = 0; i < l[n].size(); i++)
    {
        if (!lVisited[l[n][i]]) {
            lVisited[l[n][i]] = true;
            res += Ldfs(l[n][i]);
        }
    }
    return res;
}
int main() {

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int  t1 = 0, t2 = 0;
        cin >> t1 >> t2;
        //t1이 t2보다 무겁다

        h[t1].push_back(t2);
        l[t2].push_back(t1);
    }


    vector<bool> result(n + 1);
    for (int i = 1; i <= n; i++)
    {
        memset(hVisited, 0, sizeof(hVisited));
        memset(lVisited, 0, sizeof(lVisited));

        hVisited[i] = true; lVisited[i] = true;

        if (Hdsf(i) - 1 > n / 2) result[i] = true;
        if (Ldfs(i) - 1> n / 2) result[i] = true;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (result[i]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}