Baekjoon 2533. 사회망 서비스 (SNS) / Python

알고리즘 설명

문제 설명

모든 사람은 얼리 어답터이거나 얼이 어답터와 연결되어 있어야 한다.
이 때, 얼리 어답터의 최소 수를 구하는 문제

코드 설명

dp배열을 활용한다
2차원 배열을 사용하며 dp[a][0]은 노드 a 가 얼리어답터가 아닐 때의 얼리 어답터 수, dp[a][1]은 노드 a 가 얼리어답터일 때의 얼리 어답터 수를 나타낸다.
시간 복잡도 : O(n ^ 2)

from collections import deque as dq
import sys
input = sys.stdin.readline


n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]

# 인접 리스트 초기화
arr = [[] for _ in range(n + 1)]
for u, v in edges:
    arr[u].append(v)
    arr[v].append(u)

# DP 테이블 초기화
dp = [[0, 0] for _ in range(n + 1)]

# 방문 배열
visited = [False] * (n + 1)

# DFS 함수 정의
def dfs(node):
    visited[node] = True
    dp[node][1] = 1  # 현재 노드를 얼리 어답터로 선택한 경우

    for neighbor in arr[node]:
        if not visited[neighbor]:
            dfs(neighbor)
            dp[node][0] += dp[neighbor][1]  # 현재 노드를 얼리 어답터가 아닐 때
            dp[node][1] += min(dp[neighbor][0], dp[neighbor][1])  # 현재 노드를 얼리 어답터일 때

# DFS 호출 (트리의 루트는 1번 노드라고 가정)
dfs(1)

# 최종 답은 루트 노드가 얼리 어답터가 아닌 경우와 얼리 어답터인 경우 중 최소값
print(min(dp[1][0], dp[1][1]))

문제를 풀고나서 다른 방식의 구현이 떠올라서 그냥 해봤다...

1개만 연결되어 있는 노드를 찾고, 그 노드가 얼리어답터면 자식노드를 방문 처리, 꺼져있으면, 자식노드를 얼리어답터로 만들고 방문처리 하는 방식이다.

from collections import deque as dq
import sys; input = sys.stdin.readline

n = int(input())

# 각 노드의 인접 리스트를 초기화한다. 
tree = [[] for _ in range(n + 1)]

# 트리의 엣지를 입력받아 인접 리스트를 구성한다.
for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# 방문 상태를 나타내는 배열과 얼리 어답터 상태를 나타내는 배열을 초기화한다.
visit = [0 for _ in range(n + 1)]
adapted = [0 for _ in range(n + 1)]

# BFS를 위한 큐를 초기화한다.
q = dq()

# 리프 노드(자식이 없는 노드)를 찾는다. 리프 노드는 아이디어를 받아들이기 위해서는 얼리 어답터여야 한다.
for i in range(1, n + 1):
    if len(tree[i]) == 1:
        q.append(i)
        visit[i] = 1

# BFS를 수행하여 리프 노드로부터 시작한다.
while q:
    now = q.popleft()
    # 현재 노드가 더 이상 탐색할 엣지가 없다면 건너뛴다.
    if not tree[now]:
        continue
    # 현재 노드의 부모 노드를 찾는다.
    leaf = tree[now].pop()
    tree[leaf].remove(now)
    # 부모 노드가 더 이상 리프 노드인지 확인한다.
    if len(tree[leaf]) == 1:
        q.append(leaf)
    # 현재 노드가 얼리 어답터일 경우, 부모 노드를 얼리 어답터로 설정한다.
    if adapted[now]:
        continue
    adapted[leaf] = 1

# 얼리 어답터의 수를 출력한다.
print(sum(adapted))

 

시간 복잡도는 같지만, 가지치기 과정에서 시간이 조금 줄은 듯 하다.