[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)

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

풀이

• 인하니카 공화국의 수도는 1번 정점(문제에서는 0번으로 인덱싱)이다.
• 나머지 모든 정점은 루팡에 의해 공격받을 수 있고, 이들을 방어하기 위해 일부 간선에 폭탄을 설치해야 한다.
• 폭탄은 정점에 도달하는 가장 짧은 경로에 설치되고, 그 간선의 최소 비용이 사용된다.
• 최소한의 비용으로 모든 리프 노드를 보호하려고 할 때, 그 비용을 구하는 문제다.

1. 입력 및 그래프를 구성한다.

N, M = map(int, input().split())
adj = [[] for _ in range(N)]

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

adj[u] = [(v, w), …] 을 인접리스트 형식 그래프로 구성하는데 0-Based indexing으로 처리한다.

1. DFS + DP 를 구성한다.

visit = [False] * N
D = [0] * N

visit은 방문 체크용이며, D[u]는 정점 u를 루트로 하는 서브트리에서 리프를 방어하기 위한 최소 비용이다.

1. DFS 함수를 구현한다.

def dfs(u) :
    visit[u] = True

    is_leaf = True
    for v, w in adj[u] :
        if not visit[v] :
            dfs(v)
            D[u] += min(w, D[v])
            is_leaf = False
    
    if u != 0 and is_leaf :
        D[u] = 1e9

모든 자식 노드에 대해서 dfs를 수행한뒤, 해당 간선의 가중치와 D[v] 중 더 작은 값을 더한다.
즉, 간선에 폭탄을 설치할 지, 자식 쪽에서 더 싸게 설치하는 게 나을지 비교한다.
is_leaf가 True라는건 리프 노드라는 뜻이고, 리프 노드는 테러범의 공격 대상이므로 D[u] = 1e9로 설정해 최대한 큰 값으로 강제적으로 설치를 유도한다.

dfs(0)
print(D[0])

루트에서 시작해 트리를 돌고, D[0]에는 전체 최소 비용이 저장된다.

코드

# 백준 12784 - 인하니카 공화국
# 분류 : 다이나믹 프로그래밍

T = int(input())
for _ in range(T) :
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]

    for _ in range(M) :
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((b, c))
        adj[b].append((a, c))
    
    visit = [False] * N
    D = [0] * N

    def dfs(u) :
        visit[u] = True

        is_leaf = True
        for v, w in adj[u] :
            if not visit[v] :
                dfs(v)
                D[u] += min(w, D[v])
                is_leaf = False
        
        if u != 0 and is_leaf :
            D[u] = 1e9
    
    dfs(0)
    print(D[0])