[백준/파이선] 24230번 트리 색칠하기

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

24230번: 트리 색칠하기

문제가 조금 복잡하기 쓰여있지만, 하얀 색으로 칠할 수 없고 모든 입력이 칠할 수 있는 경우로만 주어지므로 그렇게 어렵게 생각하지 않아도 될 듯 하다.

 

기본적인 트리 탐색 알고리즘인 dfs와 bfs 중 하나 골라서 풀어도 되는데, 필자는 bfs로 골랐다.

핵심은 바로 부모와 나(자식)의 색깔 차이이다. 부모와 색이 다르다면 무조건 색을 한번 칠해야 하므로 그럴 때 마다 카운트를 해주면 된다.

 

그런데 유의할 점이 하나 있다. 아래 알고리즘은 첫 시작 노드를 검사해주지 못한다! 그렇기 때문에 시작 노드인 1에 색을 칠해줘야 하는지만 따로 체크해주면 된다.

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def painting(start):
  global cnt
  q = deque()
  q.append(start)
  visited[start] = True
  
  while q:
    parent = q.popleft()
    
    for i in tree[parent]:
      if not visited[i]:
        visited[i] = True
        q.append(i)
        if colors[i] != colors[parent]:
          cnt += 1

if __name__ == "__main__":
  n = int(input())
  colors = [0] + list(map(int, input().split()))
  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)
  
  cnt = 0
  visited = [False] * (n+1)
  if colors[1] !=0 :
    cnt +=1
  painting(1)
  print(cnt)