12784번 - 인하니카 공화국
1
7 6
3 2 1
2 4 1
2 1 3
1 5 4
5 6 1
6 7 1
ans : 3
"1번섬을 제외한 다리가 하나밖에 없는 어느 섬" --> leaf 노드
진이 1번 섬에서 살고있으므로 "모든 leaf노드"에서 1번 노드까지 가는 경로들에 대해서 다이너마이트 개수의 합이 최소인 경로를 끊는다고 생각하시면 편할 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
tjdvyzl12 4년 전
1
7 6
3 2 1
2 4 1
2 1 3
1 5 4
5 6 1
6 7 1
ans : 3
"1번섬을 제외한 다리가 하나밖에 없는 어느 섬" --> leaf 노드
진이 1번 섬에서 살고있으므로 "모든 leaf노드"에서 1번 노드까지 가는 경로들에 대해서 다이너마이트 개수의 합이 최소인 경로를 끊는다고 생각하시면 편할 것 같습니다.