290. 구슬 찾기
1. 위상정렬, DFS
import sys
from collections import defaultdict
N, M = tuple(map(int, sys.stdin.readline().split()))
# 1단계: 정방향 인접 리스트와 역방향 인접 리스트를 각각 생성
adj_f = defaultdict(list) # forward
adj_b = defaultdict(list) # backward
for _ in range(M):
v1, v2 = tuple(map(int, sys.stdin.readline().split()))
adj_f[v1].append(v2)
adj_b[v2].append(v1)
# print(adj_f)
# print(adj_b)
# 2단계: DFS 함수 생성
def DFS_visit(adj, v1, parent, results):
if v1 in adj:
for v2 in adj[v1]:
if v2 not in parent:
parent[v2] = v1
DFS_visit(adj, v2, parent, results)
results.append(v1)
# 3단계: 각 정점을 시작점으로 DFS를 실행했을 때, 해당 정점의 자손 개수를 카운트
answers = set()
for v1 in range(1, N+1):
# 정방향 그래프 탐색 (오름차순)
parent, results = {}, []
parent[v1] = None
DFS_visit(adj_f, v1, parent, results)
# print(v1, results)
# 본인을 제외한 자손들의 수 확인
# - 본인 제외 자손들의 수가 (N+1)//2 이상이면 본인은 가운데에 올 수 없음
# - 가령, 구슬이 5개일 때, 자손이 3개 이상이면 본인의 인덱스는 중간인 2보다 커짐
if len(results)-1 >= (N+1)//2:
answers.add(v1)
continue
# 역방향 그래프 탐색 (내림차순)
parent, results = {}, []
parent[v1] = None
DFS_visit(adj_b, v1, parent, results)
# print(v1, results)
if len(results)-1 >= (N+1)//2:
answers.add(v1)
print(len(answers))
Author And Source
이 문제에 관하여(290. 구슬 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/290.-구슬-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)