[Python] 25512번 트리를 간단하게 색칠하는 최소 비용

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

25512번: 트리를 간단하게 색칠하는 최소 비용

---

 

24/02/08

 

 

간단한 그래프 탐색 문제로, 트리의 성질을 이용한 교육적인 좋은 문제다.

---

 

문제 접근 방식:

 

 

트리를 색칠할 수 있는 최소 비용을 문제에서는 요구하고 있고, 인접한 노드마다 항상 다른 색깔로 칠해야 한다는 제약 조건이 걸려있다.

 

요지는, 트리는 이분 그래프라는 점이다.

 

트리는 이분 그래프이기 때문에, 루트를 중심으로 하여 루트를 흰색으로 칠할 지 검은색으로 칠할 지만 결정한다면 남은 노드들의 색깔은 자동적으로 정해진다,

 

때문에 이를 이용해서, 루트를 흰색으로 칠했을 때의 비용, 검은 색으로 칠했을 때의 비용을 각각 계산하여 둘 중 작은 것을 출력하면 된다.

 

나는 그래프 탐색을 할 때 BFS를 활용하여 구현했다.

     

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 25512번 트리를 간단하게 색칠하는 최소 비용
# 트리, 그래프 이론, BFS
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    p, c = map(int, input().rstrip().split())
    graph[p].append(c)
    graph[c].append(p)
cost = [[] for _ in range(N)]
for i in range(N):
    w, b = map(int, input().rstrip().split())
    cost[i] = [w, b]

def BFS(graph, cost, color):
    visited = [0 for _ in range(N)]
    total_cost = 0
    queue = deque()
    visited[0] = 1
    queue.append((0, color))
    total_cost += cost[0][color]
    while queue:
        node, color = queue.popleft()
        for near_node in graph[node]:
            if visited[near_node] == 0:
                visited[near_node] = 1
                total_cost += cost[near_node][color^1]
                queue.append((near_node, color^1))
    return total_cost

print(min(BFS(graph, cost, 0), BFS(graph, cost, 1)))