[WEEK03] 22일차. 구슬 찾기

백준 2617 구슬 찾기

무거운 구슬, 가벼운 구슬 순서로 구슬이 총 N개(홀수) 주어지는데
무게 순으로 절대 가운데 값이 될 수 없는 구슬의 개수를 찾는 문제다.

무거운 구슬과 가벼운 구슬을 따로 그래프에 넣어주고
dfs를 통해 더 무거운 구슬의 개수, 더 가벼운 구슬의 개수를 카운트해서
중간값인 (N+1)/2보다 카운트가 크거나 같을 때, answer에 하나씩 더해준다.
(N이 5일때 자신보다 크거나 작은 구슬 개수가 3이상이면 가운데 값이 될 수 없기 때문)

코드

from sys import stdin

def dfs(arr, n):
    cnt = 0
    for i in arr[n]:
        if not visited[i]:
            visited[i] = True
            cnt += 1 + dfs(arr, i)
    return cnt

N, M = map(int, stdin.readline().split())
heavier = [[] for _ in range(N+1)]  # 무거운 구슬
lighter = [[] for _ in range(N+1)]  # 가벼운 구슬
mid = (N+1) / 2  # 개수 기준 중간값

for i in range(M):
    a, b = map(int, stdin.readline().split())
    heavier[b].append(a)
    lighter[a].append(b)

answer = 0
for i in range(1, N+1):
    visited = [False] * (N+1)
    cnt = dfs(heavier, i)
    if cnt >= mid:
        answer += 1
    cnt = dfs(lighter, i)
    if cnt >= mid:
        answer += 1

print(answer)