[ 백준 2617번 ] 구슬찾기 파이썬

---

[백준 2617번 구슬찾기 바로가기]

2617번: 구슬 찾기

논리

1. 같은 함수를 사용하기 위해 인접행렬을 2개 만든다(무거운 순서, 가벼운 순서; transpose 관계)
2. 각 노드마다 dfs를 통해 하위 노드의 개수를 파악한다(무거운 순서, 가벼운 순서 2번 진행)
3. 노드 중 가벼운 것의 개수나 무거운 것의 개수가 중간 초과일 경우 이는 불가능한 노드 --> 개수 파악

코드

import sys


def counting(N: int, graph: list[list[int]]) -> list[int]:
    """count number of child nodes"""

    def _dfs(curr: int):
        visited[curr] = True    # 방문처리
        cnt = 0
        for next in range(1, N+1):
            # 현재 노드의 하위 노드 중 방문하지 않은 노드 방문
            if graph[curr][next] and not visited[next]:
                cnt += (_dfs(next) + 1)     # 하위 노드 수 + 자기 자신
        return cnt

    results = [0] * (N+1)

    # 노드마다(1..N) child node 개수 기록
    for i in range(1, N+1):
        visited = [False] * (N+1)
        results[i] = _dfs(i)
    return results


###############################
# input
N, M = list(map(int, sys.stdin.readline().split()))
bigger = [[0] * (N + 1) for _ in range(N + 1)]
smaller = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    num1, num2 = list(map(int, sys.stdin.readline().split()))
    bigger[num1][num2] = 1
    smaller[num2][num1] = 1
################################


nums_bigger_than = counting(N, bigger)
nums_smaller_than = counting(N, smaller)

imposibles = 0
bd = (N+1) // 2     # 경계값: 중간값 까지의 개수
for i in range(1, N+1):
    # i보다 작은수, i보다 큰수가 경계값 이상일 경우
    if nums_smaller_than[i] >= bd or nums_bigger_than[i] >= bd:
        imposibles += 1

print(imposibles)