[BOJ 24545] 백준 24545번 - Y

		2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 풀이
A		[BOJ 24542] 튜터-튜티 관계의 수
C		[BOJ 24544] 카카오뷰 큐레이팅 효용성 분석
D		[BOJ 24545] Y
G		[BOJ 24548] 도로 정보
K		[BOJ 24552] 올바른 괄호
L		[BOJ 24553] 팰린드롬 게임

1. 문제

$24545$. Y (2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter) Open Contest D번)

백준 24545번 - Y (https://www.acmicpc.net/problem/24545)

2. 풀이

문제의 조건 $1,\, 2,\, 3$을 토대로, 하나의 중심점에서 세 방향으로 쭉 뻗어나가는 모양을 Y-트리로 정의했음을 알 수 있다. (말 그대로 Y 모양 트리이다.)

주어진 트리에서 정점을 $0$개 이상 삭제하여 만들 수 있는 가장 큰 Y-트리의 크기를 구해야 하는 문제이다.

주어진 트리에서 정점을 최적으로 하나하나 제거하면서 가장 큰 Y-트리를 만들기는 쉽지 않다. 따라서 주어진 트리에서 바로 최대한 큰 Y-트리를 찾는 방식으로 구현한다.

Y-트리는 중심점을 기준으로 세 방향으로 쭉 뻗어 나가는 형태이다. 이 세 방향의 노드들이 최대한 길어야 가장 큰 Y-트리가 된다. 이때, 세 방향이 아닌 두 방향으로만 생각하면 이것이 ‘트리의 지름’을 의미한다는 것을 알 수 있다.

트리의 지름 문제는 백준에 실려있다. (트리의 지름 = 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것)

트리의 지름 문제 (https://www.acmicpc.net/problem/1167)

주어진 그래프에서 트리의 지름을 찾는다. 트리의 지름을 찾는 방법은 다음과 같다.

1. 임의의 정점 $A$를 고른다.
2. $A$에서 가장 먼 정점 $B$를 찾는다.
3. $B$에서 가장 먼 정점 $C$를 찾는다.
4. $B\sim C$의 길이가 트리의 지름이 된다.

첫 번째 그림의 그래프에서 이와 같은 과정을 거쳐, 양 끝 노드 번호와 트리의 지름이 $6$임을 알아낼 수 있다.

이제 나머지 한 방향을 알아내야 Y-트리가 완성된다. 이는 트리 지름의 경로에서 가장 길게 뻗은 하나의 경로를 고르면 해결된다.

지름의 양 끝 노드를 알기 때문에 이를 토대로 경로를 찾는 함수를 구현 가능하다. 세번째 그림처럼 트리 지름 경로에서 가장 길게 뻗은 $3$ 길이의 하늘색 경로가 나머지 한 방향이 된다.

그렇게 네번째 그림의 Y-트리가 완성된다.

3. 채점 결과

4. 회고

.

5. 코드