이번 문제는 플로이드-와샬 알고리즘을 통해 해결하였다. 데이터를 인접 행렬 형태로 저장하였고, 이때 graph[무거운 구슬][가벼운 구슬]에 해당하는 값만 1로 갱신하였다. 그리고 플로이드-와샬을 통해 모든 구슬간의 관계에 대한 인접 행렬을 완성하였고, 이를 y축과 x축을 확인하여 1의 갯수가 n의 절반보다 큰 경우에만 결과 변수를 1 증가시키는 방식으로 해결하였다.

Code

n, m = map(int, input().split())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if not graph[i][j]:
                if graph[i][k] and graph[k][j]:
                    graph[i][j] = 1
mid = n//2
answer = 0
for i in range(1, n+1):
    y_cnt = 0
    x_cnt = 0
    for j in range(1, n+1):
        if graph[j][i] == 1:
            y_cnt += 1
        if graph[i][j] == 1:
            x_cnt += 1
    if y_cnt > mid or x_cnt > mid:
        answer += 1
print(answer)