[BOJ 24232] 백준 24232번 - 망가진 나무

		2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 풀이
A		[BOJ 24228] 젓가락
B		[BOJ 24229] 모두싸인 출근길
C		[BOJ 24230] 트리 색칠하기
D		[BOJ 24231] 해석
E		[BOJ 24232] 망가진 나무

1. 문제

$24232$. 망가진 나무 (2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! Open Contest E번)

백준 24232번 - 망가진 나무 (https://www.acmicpc.net/problem/24232)

2. 풀이

한 노드에서의 정답을 알고 있다면, 그 노드의 인접한 노드로 이동하면서 이용하는 간선의 정보를 통해 다음 노드의 정답을 효율적으로 구할 수 있다. 이는 트리에서의 Dynamic Programming(다이나믹 프로그래밍)이다.

먼저 임의의 노드를 잡아서 정답을 구한다. 아래 그림에서 볼 수 있듯이, $1$번 노드를 잡았고 뒤집어야 하는 간선은 총 세 개이다. 그 다음, $1$번 노드의 인접한 노드인 $3$번 노드로 이동한다. 이때, 이용한 간선의 방향에 따라 다음 답이 결정된다.

이용한 간선의 방향이 역방향 $\rightarrow$ 이동한 후에는 정방향 $\rightarrow$ 뒤집어야 하는 간선 개수 $-1$

이용한 간선의 방향이 정방향 $\rightarrow$ 이동한 후에는 역방향 $\rightarrow$ 뒤집어야 하는 간선 개수 $+1$

이런 식으로 모든 노드를 탐색해서 뒤집어야 하는 개수의 최솟값이 되는 경우를 구하면 된다.

3. 채점 결과

4. 회고

.

5. 코드