https://www.acmicpc.net/problem/24545
문제 요약
- 트리가 주어짐(N = 10만)
- 가장 큰 Y-트리의 크기를 구하기
- 문제에 특징은 주어짐
- Y 모양의 특징 : 끝점 3개, 가운데 가지 3개 모이는 곳, 나머지는 그냥 노드
접근법
- 가장 긴 3개의 가지를 선택한다는 마음으로 직접적으로 접근함
- 일단 자식중에 가장 긴 것, 그 다음 긴 것, ...이 무엇인지는 알겠음 : DFS 이용
- 그런데 부모로부터 오는 가지는 어떻게 고려함?
- 다른 DFS를 수행하면서 가지고 오면 되겠는데
- 부모에서 사용한 값을 이용하면 되겠는데, 내려오는 쪽 가지는 제외해야겠고...생각할 것이 많음
- 그리고 반드시 부모에서 내려오는 것이 최대가 아니기도 함. 다른쪽 자식에서 걸쳐서 오는 것이 최대값일수도 있음
구현
- DFS1
- 1번노드가 루트라고 가정하고 진행함
- 트리를 탐색하면서 자식들에서 가장 길게 뻗쳐나가는 길이들을 크기순으로 정렬한다.
- 3개만 유지해도 되지만, 그냥 자식별로 다 모아서 정렬처리함
- 그리고 부모에게는 가장 긴것 + 1을 해서 알려주면, 부모 입장에서는 나를 통했을때 가장 길게 뻗쳐나가는 값을 참조할 수 있을 것이다
- 인접노드가 1개인 것은 별도 처리함
- DFS2
- 인접노드가 3개이상인 것들에서 가장 긴 3개의 가지를 찾는 작업을 수행한다
- 1번노드부터 탐색을 수행한다
- 자식중에서 가장 긴 것 3개를 찾는것은 어렵지 않은데, 부모로부터 오는 것을 찾는 것이 어렵다
- 루트
- 루트입장에서는 자식중에 긴것 3개를 찾으면 됨
- 자식이 2개이하면 처리하지 않음
- 루트 바로 다음 자식
- 루트 아래에 A, B, C, D 노드가 있고, A 노드를 탐색한다고 보면
- A의 부모에서 올 수 있는 것은 (B, C, D) -> 루트 -> A 가 되므로 B, C, D 중에 제일 긴것이 무엇인지 알면되고 다음처럼 구함
- 그러면 A를 제외하고 최대값을 찾기 위해서, (자식, 가장 긴 가지의 길이)와 같은 자료구조로 값을 저장하고 어느 가지로 이동하는지를 판단해야하는데 너무 귀찮음
- 그냥 최대값과 A 쪽 거리를 비교해서 같으면 다음 값을 쓰는 방식으로 진행함(최대값이 유일하든, 두개 이상이든 생각해보면 문제없음)
- 이렇게 구한 값과 A의 자식에서 긴 값들중 가장 긴 것 3개를 구함
- 루트 바로 다음 다음 자식, P라고 부르겠음
- A의 부모로부터 올 수 있는 가장 긴 가지는 알겠음
- A의 자식으로 갈때도 과연 이 값이 유효한가?
- 아닐 수도 있음
- A의 다른쪽 자식 -> A -> P로 가는게 더 길 수도 있음
- 이를 판단하기 위해서 A의 자식들의 길이에서 P를 제외하고 나머지 것들중 가장 긴 것과, A의 부모에서 왔던 값과 비교해서 큰 값을 채택
- 이 값이 P 입장에서는 부모에서 오는 것중 가장 긴 값임
- 나머지는 앞서 진행한 것과 동일
다른 접근법 - 트리의 지름을 이용해서 Y 트리의 한쪽 끝을 구하고 진행하면 된다고 함
newbieski