여행자의 책

import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def solution(): n = int(input()) # 노드 100,000개는 log_2(100,000) = 16.xxx # 16개 색깔로 색칠 가능하다. # dp[i][color] : i번째 노드를 color로 색칠했을 때 최소값 dp = [[0] * 16 for i in range(n)] #방문 여부를 체크해준다. visit = [False for i in range(n)] #인접 리스트로 트리의 간선을 기록해준다. tree = [[] for i in range(n)] for i in range(n - 1): a, b = map(int, input().split()) tree..

문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, ..