백준 / 1398 / 동전 문제 / python

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

def dfs(node, graph):
    global cnt
    cnt += 1
    visited[node] = True

    for n in graph[node]:
        if not visited[n]:
            dfs(n, graph)
    

l_g = [[] for _ in range(n+1)]
h_g = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    l_g[a].append(b)
    h_g[b].append(a)

result = 0
for i in range(1, n+1):
    cnt = 0
    visited = [False] * (n+1)
    dfs(i, l_g)

    if cnt > (n+1) //2:
        result += 1

    cnt = 0
    visited = [False] * (n+1)
    dfs(i, h_g)

    if cnt > (n+1) //2:
        result += 1

print(result)

dfs로 해결한 문제
작아지는 경우에 대한 graph 커지는 경우에 대한 graph를 각각 따로 만든다.

작아지는 경우와 커지는 경우에 대해 dfs를 진행하면서 진행한 횟수를 저장해 나간다. 저장된 dfs 진행 횟수가 주어진 n+1 // 2보다 큰 경우는 중간 값이 될 수 없는 경우이다. 이 경우에 결과 값을 더해준다.