백준 2617번 python 풀이 - 구슬 찾기

문제 링크

2617번

해결책

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())

"""
아이디어 정리
A번 구슬보다 무겁거나 가벼운 것이 N//2+1 개 이상이면...!
만약 5개의 구슬이 있다면, A 구슬보다 무겁거나 가벼운 것이 3개 이상인 경우
A 구슬은 절대 중앙이 될 수 없다.
이러한 방식으로 하면 되지 않을까?
"""


def dfs(idx):
    stk = [idx]
    is_visited = [False for _ in range(N + 1)]
    more_cnt = -1
    is_visited[idx] = True
    while stk:
        cur = stk.pop()
        more_cnt += 1
        if more_cnt >= piv:
            return True

        for path in path_heavier[cur]:
            if is_visited[path] is False:
                stk.append(path)
                is_visited[path] = True

    stk = [idx]
    is_visited = [False for _ in range(N + 1)]
    less_cnt = -1
    is_visited[idx] = True
    while stk:
        cur = stk.pop()
        less_cnt += 1

        if less_cnt >= piv:
            return True

        for path in path_lighter[cur]:
            if is_visited[path] is False:
                stk.append(path)
                is_visited[path] = True
    return False


weight = [[0, 0] for i in range(N + 1)]
path_lighter = [[] for i in range(N + 1)]
path_heavier = [[] for i in range(N + 1)]
piv = N // 2 + 1
ans = 0

for _ in range(M):
    more, less = map(int, sys.stdin.readline().rstrip().split())
    if more not in path_heavier[less]:
        path_heavier[less].append(more)
    if less not in path_lighter[more]:
        path_lighter[more].append(less)

for num in range(1, N + 1):
    if (dfs(num)):
        ans += 1

print(ans)

주석으로 달 설명

DFS로 풀었다. 양방향으로 각각 DFS를 이용해서 완전탐색을 통해, 특정 노드보다 큰 전체를 탐색, 갯수 파악을 진행하였다.