[백준 / python] 2617: 구슬 찾기

문제

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

출력

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.

풀이

N개의 구슬(N은 홀수) 중 어떠한 구슬이 ((N-1) / 2)+1 개의 구슬의 무게보다 크거나, ((N-1) / 2)+1 개의 구슬의 무게보다 작다면 그 구슬의 무게는 중간이 절대로 될 수 없다.

따라서 특정 구슬보다 무게가 크거나, 작은 구슬의 개수를 구해주고, 값을 비교하여 판단해주면 되는 문제이다.

import sys

N, M = map(int, sys.stdin.readline().split())
graph = [set() for _ in range(N + 1)]
r_graph = [set() for _ in range(N + 1)] # 역방향 그래프

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].add(b)
    r_graph[b].add(a)

def get_count(node, cur_graph, cur_visited):
    count = 1
    cur_visited.add(node)
    for n_node in cur_graph[node]:
        if n_node in cur_visited:
            continue
        count += get_count(n_node, cur_graph, cur_visited)
    return count

result = 0
for i in range(1, N + 1):
    result1 = get_count(i, graph, set()) - 1
    result2 = get_count(i, r_graph, set()) - 1
    max_count = (N - 1) // 2
    if max_count < result1 or max_count < result2:
        result += 1
print(result)