백준 24230 : 트리 색칠하기 (Python)

본문 링크

"""
부모노드가 색칠되어있고 자신의 색깔과 똑같다면 그냥 색칠한다.
그렇지 않으면 색칠하고 카운트 증가.
"""
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def DFS(Node): #트리의 루트노드는 항상 1.
    global count
    visit[Node]=True

    for i in Tree[Node]:

        if not visit[i]:
            if C[i-1]!=0 and C[i-1]!=C[Node-1]:
                count+=1
            DFS(i)

N=int(input())
C=list(map(int,input().split()))
Tree=[ [] for _ in range(N+1) ]
visit=[False]*(N+1) ; count=0 # 카운트 변수
for i in range(N-1):
    a,b=map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)

DFS(1)

if C[0]!=0:
    count+=1
print(count)

📌 어떻게 접근할 것인가?

문제에서 중요한 점은 2가지이다.

• 하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다.
• 모든 정점을 칠할 수 있는 입력만 주어진다.

그리고 색칠을 최소한으로 색칠하기 위해서는 위에서 아래로 색칠해야한다.

따라서 종합적으로 생각해보면 루트노드에서 자식노드로 이동하면서 색칠해야하는 구간이 생기면
무조건 색칠해주면된다. 왜냐하면 다시 자식노드로 이동했을때 다른색칠로 칠해야한다면
다른색으로 칠하면 되고 , 모든정점을 칠할수 있는 조건으로 입력이 주어지기 때문이다.

다만 주의해야할 점은 최소 색칠 횟수이다.
이는 부모노드가 색칠되어있으면 자식노드도 이미 색칠되어 있기 때문에 넘어가면 되지만
부모노드가 색칠되어있지않거나 다른색으로 색칠되어있는데 자식노드가 색칠되어야 하는 경우
색칠횟수를 증가시켜주면 된다.

✅ 코드에서 주의해야할 점

• 루트노드는 항상 1이대
• 루트노드만 색칠해야할 경우 count+1 을 적용시켜준다.