백준 12784 - 인하니카 공화국

백준 12784 - 인하니카 공화국

https://www.acmicpc.net/problem/12784

★풀이

모든 리프노드에서 루트노드까지 올 수 없게끔 간선을 자르는 수 많은 경우들 중에서 가장 적게 드는 비용을 구하는 문제이다. 노드간의 연결 정보와 비용이 주어지므로 인접리스트를 사용하는데 이 때 비용까지 추가적으로 저장해야 하기 때문에 따로 Bridge 객체를 생성하여 활용한다.

이제 입력이 모두 끝났으니 경우의 수를 모두 계산해 주어야 하는데 이때 DFS를 사용하면 모든 노드를 섬의 새수가 최대 1000개 이기 때문에 시간복잡도를 고려했을 때도 충분하다.

모든 노드를 순회한다고 했을 때 어떤 간선을 자르는 것이 비용이 적게 드는가를 어떻게 알 수 있을까?

단순히 노드들이 한줄로 이어져 있다면 그들 중에 최솟값을 갖는 간선을 자르면 된다. 하지만 여러 자식이 존재하는 노드가 있을 경우에는

부모노드와 연결되어 있는 간선 vs 자식 노드와 연결 되어 있는 간선들의 합

중에서 비용이 적게 드는 간선을 잘라야 한다. 이때 재귀적인 특성을 이용하여 생각해보면 매 노드마다 둘 중 상대적으로 적게 드는 비용을 return 해주면 종래에는 최선의 선택을 한 비용값이 return 된다. 나 같은 경우 루트 노드에 연결된 노드들을 시작점으로 설정하고 DFS를 설계했기 때문에 마지막에 그 값들을 더해주면 된다.

return c < s1+s2+s3 ? c : s1+s2+s3;

DFS의 기저조건은 연결 노드의 개수가 하나밖에 없는 경우에 자신과 부모노드 사이의 비용을 리턴하도록 설계했다.

★ 소스 코드

import java.io.*; import java.util.*; class Bridge{ int to; int cost; public Bridge(int to, int c) { this.to = to; this.cost = c; } } public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static ArrayList adj[]; public static void main(String[] args) throws IOException { // 다리가 하나밖에 없는 섬에서는 모두 1번으로 올 수가 없어야 한다. // 그런 모든 경우의 수들 중에서 가장 비용이 적게 드는 것을 골라야 한다. int T = Integer.parseInt(br.readLine()); for(int t = 0; t(); } for(int i = 0; i

"); } // T bw.flush(); } static boolean visited[]; static int dfs(int x, int cost) { if(adj[x].size() == 1) { return cost; } int sum = 0; for(Bridge next : adj[x]) { if(!visited[next.to]) { visited[next.to] = true; sum += dfs(next.to, next.cost); } } return cost < sum ? cost : sum; } }

from http://sweet-smell.tistory.com/37 by ccl(A) rewrite - 2021-08-23 21:26:14