[백준] 스크루지 민호 2

https://www.acmicpc.net/problem/12978

12978번: 스크루지 민호 2

아이디어를 생각해내는데 꽤나 걸렸던 문제입니다. 포인트는 현재 노드로부터 도달할 수 있는 리프 노드까지의 경로 길이 중에 홀수 길이가 있는지를 알아야합니다. 현재 노드로부터 홀수 경로 길이라면 현재 노드에 경찰서를 세워주면 됩니다. 호

만약, 길이가 짝수라면 자식 노드에 경찰서가 이미 세워져 있으므로 세울 필요가 없기 때문입니다.

 

import sys, heapq
from collections import deque, defaultdict

sys.setrecursionlimit(10 ** 8)
INT_MAX = sys.maxsize
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

graph = defaultdict(list)

visited = [False] * (n + 1)

for _ in range(n - 1):
    v1, v2 = tuple(map(int, input().split()))

    graph[v1].append(v2)
    graph[v2].append(v1)

ans = 0
def dfs(cur):
    global ans
    hasOddLength = False

    for next in graph[cur]:
        if not visited[next]:
            visited[next] = True
            ret = dfs(next)
            # 홀수 길이의 경로가 있다면 체크
            if ret:
                hasOddLength = True

    if hasOddLength:
        ans += 1
        
    # 현재 노드가 홀수 길이의 경로 있다면 부모 노드에서 현재노드로 오는 subtree에는 없다.
    return not hasOddLength

visited[1] = True
dfs(1)
print(ans)

 

두번째 풀이는 트리 디피를 활용한 법입니다. 현재 노드에 경찰서를 세운 경우와 경찰서를 세우지 않은 경우 두가지로 나누어서 DP를 수행해주면 됩니다. 경찰서를 세우지 않은 경우에는 반드시 다음 노드들에서 경찰서를 세워주어야하므로 dp[i][1]을 더해주어야합니다. 반대로 경찰서를 세우는 경우에는 다음 노드에 경찰서가 있든 없든 무관하므로 두개중에 더 작은 값을 더해주면 됩니다.

 

import sys, heapq
from collections import deque, defaultdict

sys.setrecursionlimit(10 ** 8)
INT_MAX = sys.maxsize
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

graph = defaultdict(list)

visited = [False] * (n + 1)

for _ in range(n - 1):
    v1, v2 = tuple(map(int, input().split()))

    graph[v1].append(v2)
    graph[v2].append(v1)

# dp[i][0]: i 노드에 경찰서를 세우지 않은 경우
# dp[i][1]: i 노드에 경찰서를 세운 경우
dp = [
    [0, 1]
    for _ in range(n + 1)
]

def dfs(cur):
    global ans

    for nxt in graph[cur]:
        if not visited[nxt]:
            visited[nxt] = True
            dfs(nxt)

            # 현재 노드에 경찰서를 세울 것이므로 다음 노드부터의 최소 경찰서의 수를 더해주면 된다.
            dp[cur][1] += min(dp[nxt][0], dp[nxt][1])
            # 현재 노드에 경찰서를 세우지 않으면 되므로 다음 노드에는 무조건 경찰서를 세워야한다.
            dp[cur][0] += dp[nxt][1]

    return

visited[1] = True
dfs(1)
print(min(dp[1]))