백준 2533: 사회망 서비스(SNS) (Python)

문제

페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 

예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 

 

친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, 사회망 서비스에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 

어떤 아이디어를 사회망 서비스에서 퍼뜨리고자 할 때, 가능한 한 최소의 수의 얼리 아답터를 확보하여 모든 사람이 이 아이디어를 받아들이게 하는  문제는 매우 중요하다. 

일반적인 그래프에서 이 문제를 푸는 것이 매우 어렵다는 것이 알려져 있기 때문에, 친구 관계 그래프가 트리인 경우, 즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다. 

예를 들어, 8명의 사람으로 이루어진 다음 친구 관계 트리를 생각해보자. 2, 3, 4번 노드가 표현하는 사람들이 얼리 아답터라면, 얼리 아답터가 아닌 사람들은 자신의 모든 친구가 얼리 아답터이기 때문에 새로운 아이디어를 받아들인다.

 

친구 관계 트리가 주어졌을 때, 모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리 어답터의 수를 구하는 프로그램을 작성하시오.

해설

'트리에서의 다이나믹프로그래밍' 태그가 붙은 문제라 고민을 많이했다.

다른 블로그 풀이들은 대부분 2차원 DP를 사용했는데 나는 조금 다른 방법으로 풀었다.

 

맨 밑의 노드부터 보면서 정답을 확정해나가며 올라가는 전략을 취했는데, 개인적으로는 이 방법이 더 직관적이고 깔끔한 것 같다.

 

❗ 풀이 과정 ❗ 

1. 모든 노드는 얼리어답터(EA) 이거나, 아니거나 둘 중 하나다.

각 노드가 EA인지 아닌지를 저장할 리스트 EA를 만들었다. EA라면 True, 아니라면 False가 저장된다.

 

위 그림의 경우 EA[2], EA[3], EA[4] 는 True, 나머지는 False이다.

 

2. 자식 노드부터 거슬러 올라가야 한다.

위와 같은 그래프가 있다고 생각해보자. 우리는 여기서 '어떤 노드가 EA가 되어야 하는지'를 결정해야 한다.

여기서 100% 확신할 수 있는 사실은 '자식이 없는 노드는 EA가 되어서는 안된다'는 것이다.

왜냐하면 자식이 없는 노드가 EA가 되는 바에야, 그 노드의 부모 노드가 EA가 되는 것이 더 이득이기 때문이다.

 

자식이 없는 4, 5번 노드를 보자. 

만약 자식이 없는 4번 노드가 EA가 되는 경우, 영향력 범위는 [자기 자신(4)+부모노드(2)] 뿐이다.

그러나 '자식이 없는 노드의 부모 노드' 가 EA가 되는 경우에는 [자기 자신(4) + 부모노드(2) + 부모 노드와 연결된 다른 노드(5)] 까지 영향력이 늘어난다.

 

어떤 상황에서라도 자식이 없는 노드는 EA가 되어서는 안된다.

그러면 우리는 이로써 트리 맨 밑단 부분의 정답을 확정할 수 있다.

 

아랫 부분의 EA 여부를 확정했으니, 이제 트리를 아래부터 거슬러 올라가며 윗 부분의 정답도 확정해주면 되는 것이다!

 

3. 자식 노드 중에 하나라도 EA가 아닌 노드가 있다면 부모 노드는 EA가 되어야 한다

 

방금 전의 과정을 통해 트리 맨 밑단의 정답을 확정했고, 그 결과 4번/5번 노드는 EA가 되어선 안된다는 사실을 알았다.

그 결과 4/5번 노드의 부모 노드인 2번 노드가 EA가 되었다. 이후 3번 노드 역시 자식 노드가 없으므로 EA가 되어선 안된다는 사실을 알았다.

만약 현재 노드가 EA가 아니라면, 부모 노드는 무조건 EA가 되어야 한다.

우리는 트리 아래부터 정답을 확정하며 올라가고 있다. 즉, 현재 노드의 EA 여부는 최적의 해임이 확실하다.

그렇다면, 현재 노드에서 만약 EA가 아니었을 때 부모 노드는 이를 상쇄하기 위해 무조건 EA가 되어야 한다.

 

"EA가 아닌 사람들은 자신의 모든 친구들이 EA일 때만 이 아이디어를 받아들인다." 는 문제 조건 때문이다.

현재 노드의 값은 100% 신뢰할 수 있다. 만약 현재 노드가 EA가 아니라면 EA가 아닌 것이다.

그렇다면 부모 노드는 !EA인 현재 노드에게 영향을 주어야만 하기에, 부모 노드가 EA가 되어야 하는 것이다.

 

 

이런 식으로 root 노드에 도달하기까지 아래부터 정답을 확정해 올라가고, EA 여부를 EA 리스트에 [True | False] 형태로 저장하면 쉽게 답을 구할 수 있다.

 

여담이지만 Pypy3 로 제출하니 시간초과가 났고 python3로 제출하였더니 통과했다.

백준 풀이 시 참고하면 도움이 될 것이다.

 

코드

from collections import deque
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def DFS(graph, nodeIdx, parentIdx):
    visited[nodeIdx] = True  # 방문처리

    for node in graph[nodeIdx]:
        if not visited[node]:
            DFS(graph, node, nodeIdx)

    if parentIdx:  # root가 아닐때
        if not EA[nodeIdx]:
            EA[parentIdx] = True


N = int(input())
graph = [[]*(N+1) for _ in range(N+1)]
EA = [False] * (N+1)  # Early Adapter
visited = [False] * (N+1)

for i in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

DFS(graph, 1, None)
print(EA.count(True))