[백준] 24230 트리 색칠하기 python

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

24230번: 트리 색칠하기

트리 문제이다.

트리를 만들고 순회하면 된다.

특정 노드의 부모가 가진 색깔과 노드가 원하는 색깔이 다른 경우 1 을 더한값을 계속 올려주면 된다.

 

import sys; input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def order(cur_node, cur_color, parent, adj_list, color):
    ret = 0
    if color[cur_node] != cur_color:
        ret += 1
        cur_color = color[cur_node]

    if not len(adj_list[cur_node]):
        return ret

    for son in adj_list[cur_node]:
        if son == parent: continue
        ret += order(son, cur_color, cur_node, adj_list, color)

    return ret

def main():
    N = int(input())
    color = [0] + list(map(int, input().split()))
    adj_list = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        adj_list[u].append(v)
        adj_list[v].append(u)

    ans = order(1, 0, -1, adj_list, color)
    print(ans)

if __name__ == '__main__':
    main()