728x90
https://www.acmicpc.net/problem/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)
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 5639번 이진 검색 트리 (0) | 2023.03.15 |
---|---|
[백준/파이썬] 1965번 상자넣기 (0) | 2023.03.14 |
[백준/파이썬] 1707번 이분 그래프 (0) | 2023.03.04 |
[백준/파이썬] 1967번 트리의 지름 (0) | 2023.02.22 |
[백준/파이썬] 1991번 트리 순회 (0) | 2023.02.18 |