[백준/Python] 24230번: 트리 색칠하기

문제

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

24230번: 트리 색칠하기

---

문제 요약

정점이 n개인 트리가 있다. 정점에는 1부터 n까지 번호가 붙어있고, 트리의 루트는 항상 1번 정점이며, 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다.

 

하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다.

+ 색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다. (단, 하얀색으로 색칠할 수는 없다.)

 

트리의 정보(연결된 정점)와 색칠해야하는 각 노드의 색 정보를 입력 받고, 하얀색을 제외한 색만 사용해서 모든 정점을 원하는 색으로 칠하기 위해 최소 몇 번 칠하면 되는지 출력한다.

---

코드

import sys
input = sys.stdin.readline

# 트리를 구성하는 정점의 개수
N = int(input()) 

# 0번 정점부터 n-1번 정점까지 각 색 정보 입력 (0인 경우 흰 색)
color = list(map(int, input().rstrip().split()))

# 인접 리스트 tree[i]: i번 노드와 인접한 노드의 정보 저장
tree = [[] for _ in range(N)]
visited = [0 for _ in range(N)]

# 연결된 정점의 정보 입력
for _ in range(N-1):
    # 람다함수를 사용하여 0 ~ n-1번으로 저장
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    tree[a].append(b)
    tree[b].append(a)

res = 0 # 색칠 횟수

stack = []
stack.append(0) # 0번 노드부터 dfs 탐색
visited[0] = 1

while stack:
    node = stack.pop()
    for near_node in tree[node]:
        if visited[near_node] == 0:
            visited[near_node] = 1
            # 인접한 노드의 색이 다르다면 인접한 노드를 새롭게 색칠해야한다.
            if color[node] != color[near_node]:
                res += 1
            stack.append(near_node)

# 처음에 0번 노드에 색을 칠한 경우
if color[0] != 0:
    res += 1

print(res)

---

코드 설명

부모와 자식간의 색깔이 같다면, 그 자식은 부모 때문에 색칠된 것으로 볼 수 있으므로 색칠 횟수를 세지 않는다.

 

1. 색칠해야 하는 각 노드의 색 정보를 입력 받아 배열 color에 저장한다.

 

2. 연결된 정점들의 정보를 입력 받아 인접리스트 tree에 저장한다.

+ tree[i]: i번 노드와 인접한 노드의 정보 저장 (0번 노드 ~ n-1번 노드)

 

3. 0번 노드부터 dfs 탐색을 시작한다.

 

3 - 1. DFS 탐색 중 한 노드와 인접한 노드들을 하나씩 비교하여 색이 다른 노드가 있다면, 새롭게 색칠해야 하므로 색칠 횟수를 증가시킨다.

 

4. 처음에 0번 노드에 색을 칠할 경우에는 색칠 횟수가 한번 더 증가시킨다.

 

5. 색칠 횟수를 출력한다.

 

< 참고 >

https://lighter.tistory.com/193