BOJ 12784 인하니카 공화국

문제에서 두 섬을 연결하는 다리의 개수를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다는 말에서 일단 트리 문제라는 것을 추측할 수 있다.

그리고 주인공이 1번 섬에 살고 있으므로 1번을 트리의 root로 보면 될 것이고,...

모든 리프노드와 루트노드와의 연결을 끊어야 하는데, 어디서 끊어야 비용이 최소화 되는지를 알아야 하므로 리프노드부터 올라오면서 끊는데 드는 비용을 비교해보고 최소값을 구해야 한다. 재귀(dfs)를 이용해서 리프노드까지 내려가서 한 노드의 자식들과 연결된 간선의 가중치의 합과 그 노드가 부모와 연결된 간선의 가중치 중 최소값들을 합해서 return 하는 식으로 하면 모든 리프노드와 루트노드의 연결을 끊는 최소 비용을 구할 수 있다.