[BOJ] 2533 사회망 서비스(SNS) (Python)

문제

2533번: 사회망 서비스(SNS)

 

 

 

풀이

- 틀린 풀이

먼저, 각 노드(사람)와 에지(친구 관계)를 나타내는 그래프를 구성합니다. 그런 다음, 각 노드의 연결 정도(친구 수)에 따라 우선순위 큐(최소 힙)를 이용하여 최소 얼리아답터의 수를 계산했습니다.

import sys
import heapq as hq
from collections import defaultdict

input = sys.stdin.readline

N = int(input())
friends = []  # 친구 수를 담는 heap
friends_size_list = [0 for _ in range(N + 1)]
graph = defaultdict(list)   # 친구 관계를 모두 담는 그래프.
ans = 0

for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    friends_size_list[a] -= 1
    friends_size_list[b] -= 1

for i in range(1, N + 1):
    if friends_size_list[i]:
        hq.heappush(friends, (friends_size_list[i], i))

while friends:
    size, node = hq.heappop(friends)
    if size != friends_size_list[node]:
        hq.heappush(friends, (friends_size_list[node], node))
        continue
    if size == 0:
        continue

    ans += 1

    for temp in graph[node]:
        if friends_size_list[temp]:
            friends_size_list[temp] += 1

    graph.pop(node)

print(ans)

1. friends 힙은 각 노드의 친구 수를 음수로 저장하여, 친구가 적은 노드부터 처리합니다. (파이썬의 heapq 모듈은 최소 힙만을 지원하기 때문에 음수를 사용합니다)
2. 각 노드에 대한 친구 수는 음수로 friends_size_list 리스트에 저장됩니다.
3. graph는 defaultdict를 사용하여 양방향 그래프를 나타냅니다.
4. 메인 루프에서는 힙에서 노드를 하나씩 꺼내어 처리합니다. 만약 현재 힙에서 꺼낸 친구 수와 실제 친구 수가 다르면, 친구 수를 갱신하여 다시 힙에 넣습니다.
5. 만약 노드의 친구 수가 0이라면, 해당 노드는 이미 처리된 것으로 간주하고 건너뜁니다.
6. 최종적으로 ans에는 필요한 최소 얼리 아답터의 수가 저장됩니다.

하지만 위와 같은 방식으로는 최적해를 구할 수 없습니다. 동일한 간선 수를 가진 노드에 대해서는 오름차순으로 순차탐색하기 때문입니다.

- 수정 코드

import sys
from collections import defaultdict

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

def solve(node):
    visited[node] = True

    for child in graph[node]:
        if not visited[child]:
            solve(child)
            dp[node][0] += dp[child][1]
            dp[node][1] += min(dp[child][0], dp[child][1])

    return min(dp[node][0], dp[node][1])

N = int(input())
graph = defaultdict(list)
dp = [[0, 1] for _ in range(N + 1)]  # index 0은 자신이 얼리어답터가 아닐 때, index 1은 자신이 얼리어답터일 때.
visited = [False] * (N + 1)

for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

print(solve(1))

tree dp로 DFS 재귀를 돌았습니다.

여기서 dp는 각 노드별로 두 가지 상태를 저장하는 배열입니다. dp[node][0]은 노드가 얼리 아답터가 아닐 때 필요한 최소 얼리 아답터 수를, dp[node][1]은 노드가 얼리 아답터일 때 필요한 최소 얼리 아답터 수를 저장합니다.
visited는 각 노드의 방문 여부를 추적하는 배열입니다.

solve 함수는 주어진 노드에서 시작하여 DFS를 수행하고, 해당 노드와 연결된 서브트리에 대해 필요한 최소 얼리 아답터 수를 계산합니다.
현재 노드가 얼리 아답터가 아니라면, 모든 자식 노드는 얼리 아답터여야 합니다(dp[node][0] += dp[child][1]).
현재 노드가 얼리 아답터라면, 각 자식 노드는 얼리 아답터일 수도, 아닐 수도 있으므로 두 경우 중 최솟값을 사용합니다(dp[node][1] += min(dp[child][0], dp[child][1])).

모든 노드를 한 번씩만 방문하기 때문에, 시간 복잡도는 노드의 수 N에 비례하는 O(N)입니다.