백준 2617 구슬찾기 / python dfs

핵심 :

• 홀수인 N개의 구슬이 주어진다.
• 자신보다 무거운 구슬의 갯수가 (N//2) + 1 개 or
• 자신보다 가벼운 구슬의 갯수가 (N//2) + 1 개

import sys

sys.setrecursionlimit(10 ** 8)

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n + 1)]
rev_graph = [[] for _ in range(n + 1)]
for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    graph[i].append(j)
    rev_graph[j].append(i)


def dfs(specific_graph, now):
    visit[now] = True
    for next in specific_graph[now]:
        if not visit[next]:
            dfs(specific_graph, next)


count = 0
for i in range(1, n + 1):
    visit = [False] * (n + 1)
    dfs(graph, i)
    if sum(visit) - 1 >= n // 2 + 1:
        count = count + 1
    else:
        visit = [False] * (n + 1)
        dfs(rev_graph, i)
        if sum(visit) - 1 >= n // 2 + 1:
            count = count + 1
print(count)

과정 :

• 입력 : 무거운 구슬의 개수를 구하기 위한 graph 와, 가벼운 구슬의 개수를 구하기 위한 rev_graph 를 동시에 입력받는다.

• dfs:

• 방문확인 배열 생성, 초기화(False)

• dfs 를 돌고 나왔을 때, visit 에서 True 값을 가진 index 는 나보다 무거운 구슬이라는 뜻임.

• 따라서, 만약에 sum(visit) -1 (나를 제외한 구슬의 개수가) n//2 + 1 (홀수개 이므로, 중앙값을 초과한 개수) 개보다 많다면 count += 1

• (무거운 개수가 1//2 +1 보다 많지 않다면), 가벼운 구슬에 대해서도 rev_graph로 dfs 를 하여 중앙값이 될 수 있는 지 없는 지 확인하여 count 에 반영한다.