https://www.acmicpc.net/problem/20927
문제 요약
- 노드별 차수 제약이 있는 상태에서 MST를 구성
- 노드 <= 10, 간선 <= 27
접근법
- 완전탐색 : 트리를 만들어야하므로 사용할 간선의 개수정해져있고, 전체에서 선택하는 문제임,
- 간선을 정하고 조건에 맞는지 확인
- 연산횟수 : 4686825 * 10 = 4천만
- 완전탐색에서 가지치기를 하면 시간은 더 줄어들 듯
- 실수했던 부분
- 트리인지 판단하기 위해서 n - 1개의 간선만 사용하고, 노드의 차수가 0인 것이 있는지를 판단했음
- 하지만 이런 접근은 틀렸음 왜냐하면
- 그래프가 두개로 나뉘면서 한쪽은 트리 한쪽은 cycle이 생길수도 있기때문임
- 바른 접근
- 사용한 간선으로 그래프를 구성해봄. union-find 사용
newbieski