백준 - 2617번 : 구슬 찾기(C++)

풀이 방법 : DFS

입력받은 정보를 단방향 그래프에 저장해준뒤 각 인덱스로부터 출발하여 깊이우선 탐색을 진행한다.

깊이우선 탐색을 통해 구슬들의 관계를 알 수 있다.

1. i번째 구슬에서 출발하여 도달할 수 있는 번호의 구슬들은 i번보다 가볍다는 뜻이다.

2. 다른 번호에서 출발하여 i번째에 구슬에 도달할 수 있는 번호의 구슬들은 i번째 보다 무겁다는 의미이다.

깊이우선 탐색을 진행해가며 check[시작지점][도달지점]을 true로 만들어주며 그 관계를 표시해나간다. 모든 탐색이 끝나면 반복문을 통해 각 구슬보다 무거운 구슬의 숫자, 가벼운 구슬의 숫자를 세준다.
만약 둘 중 하나라도 구슬 숫자의 절반을 초과할 경우 해당 구슬은 중간 무게의 구슬이 될 수 없다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

int N, M;
bool Check[501][501] = {};
bool Visit[501] = {};
vector<vector<int>> Graph;

void DFS(int Current, int Start)
{
    int Size = Graph[Current].size();

    for (int i = 0; i < Size; ++i)
    {
        int Next = Graph[Current][i];
        Check[Start][Next] = true;

        if (Visit[Next])
            continue;

        Visit[Next] = true;

        DFS(Next, Start);
    }
}

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    Graph.resize(N + 1);

    for (int i = 0; i < M; ++i)
    {
        int Src, Dest;
        cin >> Src >> Dest;

        Graph[Src].push_back(Dest);
    }

    for (int i = 1; i <= N; ++i)
    {
        memset(Visit, 0, N + 1);

        Visit[i] = true;
        DFS(i, i);
    }

    int Cnt = 0;
    for (int i = 1; i <= N; ++i)
    {
        int LeftCnt = 0;
        int RightCnt = 0;
        for (int j = 1; j <= N; ++j)
        {
            if (Check[j][i])
                ++LeftCnt;

            if (Check[i][j])
                ++RightCnt;
        }
       
        if (LeftCnt > N / 2  || RightCnt > N / 2)
            ++Cnt;
    }
    
    cout << Cnt;
}