2617번

2617번 - 구슬 찾기

DFS 알고리즘 분류 문제로 풀었는데, 이전에 플로이드로 풀었던 문제랑 비슷했다.

만약 DFS나 BFS로 풀려면 , 한 노드당 두번씩 돌려서 작은 구슬, 큰 구슬의 갯수를 구해주면 된다.

구슬의 크기가 중간일 확률이 아예 없으려면, 큰 구술이 과반이 넘거나, 작은 구슬이 과반이 넘어야 한다.

처음에 나는 이전에 풀었던 문제와 비슷하게, 큰구슬+작은구슬이 과반이 넘어가면 정답으로 체크했는데, 이 문제에서는 틀리다.

딱 중간에 있는 구슬의 경우 큰구슬+작은구슬이 과반을 넘지만, 중간이기 때문이다.

또한 짝수든 홀수든 (n/2)+1 이 반절이 된다. 만약 1 2 3 4 네개의 구슬일 경우 2,3 모두 중간이기 때문이다.

따라서 플로이드 값을 비교하면서, small 배열과 big 배열을 구해서 half 와 비교해서 크면 정답으로 체크했다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
bool D[100][100];
int main()
{
    int n, m;
    cin >> n >> m;
    int half = (n / 2) + 1;
 
    for (int i = 1; i <= n; i++)
    {
        D[i][i] = true;
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        D[a][b] = true;
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                D[i][j] = D[i][j] || (D[i][k] && D[k][j]);
            }
        }
    }
 
 
    int ans = 0;
    int big[101] = { 0, };
    int small[101] = { 0, };
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
            {
                big[i]++;
                small[i]++;
                continue;
            }
            if (D[i][j])
            {
                big[i]++;
                small[j]++;
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (big[i] > half) ans++;
        if (small[i] > half) ans++;
    }
 
    cout << ans << "\n";
    return 0;
}