[Python 파이썬] 백준 24230번 - 트리 색칠하기

2023년 4월 29일

문제 링크 : 백준 24230 - 트리 색칠하기

문제

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

하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다. 색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다. 단, 하얀색으로 색칠할 수는 없다.

아래 그림처럼 정점 10개로 구성된 트리가 있다고 가정을 해보자.

[그림 1] 하얀색으로 칠해져 있는 트리

3번 정점을 노란색으로 칠하면 그 아래 있는 정점 5, 6, 8, 9, 10 모두 노란색으로 칠해진다.

[그림 2] 정점 3에 노란색을 칠한 후 트리의 상태

그리고 정점 5에 파란색을 칠한다면 그 아래 있는 정점 8, 9, 10 모두 파란색으로 칠해진다.

[그림 3] 정점 5에 파란색을 칠한 후 트리의 상태

입력으로 트리의 정보와 정점의 색 정보가 주어진다. 색 정보는 음이 아닌 정수로 주어지며 값이 0인 경우는 항상 하얀색을 의미한다.

하얀색을 제외한 색만 사용해서 모든 정점을 주어진 색으로 칠하고 싶을 때 최소 몇 번 색을 칠해야 모든 정점을 원하는 색으로 칠할 수 있는지 구해보자.

입력

첫째 줄에 트리를 구성하는 정점의 개수 N(1 ≤ N ≤ 200,000)이 주어진다.

둘째 줄에 1번 정점부터 N번 정점까지 각 색 정보 C_i​(0 ≤ C_i ​≤ N)가 공백으로 구분되어 주어진다.

셋째 줄부터 N−1개의 줄에 걸쳐 연결된 두 정점 a,b(1 ≤ a , b ≤ N,
 a ≠ b)가 공백으로 구분되어 주어진다.  

모든 정점을 칠할 수 있는 입력만 주어진다.

출력

하얀색을 제외한 색만 사용해서 모든 정점을 원하는 색으로 칠하기 위해 최소 몇 번 칠하면 되는지 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색

 

---

문제 접근

문제가 뜻하는 바가 무엇일까. 일단 문제에서 알려준 정보들을 나열해보자.
1. 트리의 루트 노드는 항상 1번 정점이다.
2. 아무 색도 칠해지지 않았음은 '하얀색' 즉 0 으로 표기할 수 있다.
3. 특정 노드에 특정 색을 칠했다면, 해당 노드의 자식 노드들은 모두 같은 색으로 칠해진다.
4. 특정 색으로 이미 칠해져 있는 노드라도, 해당 노드의 부모 라인 노드가 다른 색으로 칠해진다면, 해당 색으로 덧씌워진다.(색이 부모의 색을 따라간다.)

부모 노드의 색과 자식 노드의 색이 다를려면, (1) 부모 노드 색을 칠한다. (2) 자식 노드 색을 칠한다 순서로 진행되어야 할 것이다. (반대 순서로 진행한다면, 자식 노드가 무슨 색을 칠하던, 부모 노드가 색을 칠하는 순간, 색이 덮어씌워져 의미가 없어질 것이다.)

 

4번 정보를 보았을 때, 트리의 최종 색 배열 중 '부모 노드의 색' 과 '자식 노드의 색'이 다르다면, 부모노드 1번 칠함 -> 자식노드 1번 칠함의 흔적이라고 볼 수 있기에, '최소 색을 칠한 횟수'를 1씩 증가시켜 답을 구할 수 있을 것이다.

 

---

순서도

 

1. 데이터들을 입력받는다.
	1-1. tree는 연결리스트 형태로 입력받음
    	1-2. tree 리스트의 size는 N+1로 하되, 0번째 인덱스는 더미값으로 둔다.
        
2. 최종적으로 출력해야 하는, 색칠하는 최소 횟수를 담을 cnt 변수를 선언한다. (초기값 : 0) 

3.  DFS를 통해 노드 방문 시, 중복 방문을 막기 위한 visited 리스트 선언. (초기값 : False, size : N+1, 0번째 인덱스는 더미값)

4. 각 노드의 최종 색 배열을 color 리스트에 입력받음.
	4-1. color 리스트의 맨 앞(0번째 인덱스) 위치에 더미값 0을 대입한다.

5. DFS 메소드를 호출하여 탐색을 진행한다.
	5-1. 부모노드와 자식노드의 색이 다르면 cnt를 1 증가시킨다.

6. 최종 cnt 값을 출력한다.

---

입력 예제

7
0 0 2 0 1 2 2
1 2
1 3
1 4
2 5
3 6
3 7

입력 예제는 다음과 같다
1. 노드는 1~7번까지 총 7개이다.
2. 1~7번 노드 각각은 현재 입력받은 색을 지니고 있다.
3. 6줄에 걸쳐 각 노드간의 연결관계가 주어진다.

입력 예제로 받아온 정보를 바탕으로 트리를 그려보면 다음과 같다.

위 예제는 적어놓은 바와 같이, 모든 노드의 색이 0(하얀색)인 상태에서, (1) 5번 노드에 1(ex. 빨간색)을 칠하고, (2) 3번 노드에 2(ex. 파란색)을 칠하면 최종 트리 모양이 완성된다.

출력 예제

2

 

그렇다면, 다음과 같은 트리가 되려면 총 몇 번 색을 칠해야 하는가?

첫 예시 결과의 트리에서, 6번 노드에 빨간색을 추가로 칠했으며, 결과는 보시다시피, 위 트리에서 한 번 더 색을 칠했기에, 최소 3번 색을 칠해야위와 같은 트리 모양이 완성된다.
여기서 알 수 있는 이 문제의 핵심은, "특정 노드의 색과, 특정 노드의 부모 색이 다르다면", 색을 최소 1회 더 칠한 결과물이라는 것이다.
만약 7번 노드도 빨간색으로 칠했다면, 부모 노드인 3번 노드와 색이 다르기에, 1회 더 합산하여 최소 4회 색을 칠해야 함을 알 수 있다.

---

주의할 점

1. 입력받을 수 있는 최대 노드의 개수 N은 200,000으로, 트리의 깊이는 최대 200,000까지 가능하다. DFS를 통해 재귀호출되는 횟수도 최대 200,000회 이므로, 재귀 깊이 제한을 200,000으로 늘려주어야 한다.

---

전체 코드

# 24230

'''
예상 풀이 과정
1. 입력 받음. 트리는 연결리스트 형태로 받는다.
2. dfs를 통해 부모와 자식의 색이 다르면, cnt를 1증가
3. dfs가 끝났을 때, cnt 값을 출력
'''

import sys
sys.setrecursionlimit(200000) # 최대 재귀 호출 횟수 : N = 200,000
input = sys.stdin.readline

def dfs(p_node,c_node): # 매개변수 : 부모노드, 자식노드
    global tree
    global visited
    global cnt

    visited[c_node] = True # 방문한 노드 기록
    '''
    부모 노드의 색과 자식 노드의 색이 다르면 색을 1회 더 입혔다는 의미
    ex) p_node = 1, c_node = 2
    1. p_node를 1로 칠하면 c_node는 자연스럽게 1로 칠해짐
    2. c_node가 2로 칠해지는 행위가 한 번 더 이루어 졌기에, c_node는 p_node와 다른 2가 가능
    '''
    if color[p_node] != color[c_node]:
        cnt += 1
    # 자식 노드 방문
    for i in tree[c_node]:
        if visited[i] == False:
            dfs(c_node,i)

if __name__ == "__main__":
    N = int(input()) # 정점 개수

    cnt = 0 # 총 색칠하는 횟수

    # tree 선언. 0번째 인덱스는 더미 값
    tree = [[] for _ in range(N + 1)]
    
    # 노드 방문 여부 판단
    # 0 : 방문 안함
    # 1 :방문 함
    # 0번째 인덱스는 더미 값
    visited = [False] * (N+1)

    #각 정점의 색 입력받기. 0번째 인덱스는 더미 값
    color = list(map(int,input().split()))
    color.insert(0,0)

    # 각 정점의 연결관계를 연결리스트로 표현
    for _ in range(N-1):
        a,b = map(int,input().split())
        tree[a].append(b)
        tree[b].append(a)
    
    # 초기 p_node : 0, c_node : 1
    dfs(0,1)
    print(cnt)

---

풀이 후기

문제의 핵심인, 부모노드와 자식노드의 색이 다를 때마다 cnt를 1씩 증가시켜주는 부분을 캐치한다면, 어렵지 않게 풀 수 있는 문제라고 생각한다.