https://www.acmicpc.net/problem/19535
문제요약
- 트리에서 ㄷ요소와 ㅈ요소의 개수를 세고 결과를 출력
접근법
- 인접 노드 카운트를 센다 : incnt
- ㅈ요소는 icnt >= 3인 것 중에서 을 하면됨
- ㄷ요소는 착각을 했음
- dfs로 탐색을 하면서 노드의 하위에 연속으로 3개가 있는 것들의 경우의 수를 합해가는 방식. [3, 2, 1, 0] 가지수를 저장해가는... dp같이
- 오류 이유 : 노드를 "걸쳐서" ㄷ요소가 가능함 예를 들어 A노드의 한쪽은 1개로 이어져있고, 다른쪽은 2개로 이어져있는 경우
- 엄밀하게 하려고 했으면 A 노드를 기준으로 한쪽 1개, 다른쪽 2개를 저장해놓고 곱하기로 가야하는데.....구현이 복잡해짐
- 쉬운 접근법 (다른 사람 풀이 참고)
- ㄷ요소는 간선이 3개임. 가운데 간선에 집중해보면
- 가운데 간선 양쪽 노드는 incnt가 2 이상일 것임
- 즉 가운데 간선으로 만들수 있는 ㄷ요소를 세어나가면 됨
newbieski