[백준][7812] 중앙 트리

[백준][7812] 중앙 트리

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	128 MB	651	221	135	28.361%

문제

트리는 사이클을 갖지 않는 연결된 그래프이다.
중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점이다. 트리의 정점 개수가 작은 경우에는 모든 경우의 수를 다 계산해보는 프로그램을 이용해 쉽게 구할 수 있다.

위의 그림은 가중치가 있는 트리로, 정점의 개수는 5개이다. 이 트리의 중앙 정점은 B이다.
B-A = 2, B-D = 7, B-C = 1, B-E = 7+5=12, 총: 2+1+7+12 = 22
N이 큰 경우에 문제를 풀어보자.
트리를 입력 받아, 모든 정점과 중앙 정점까지 비용의 합을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄에는 세 정수 a, b, w가 주어진다. (1 ≤ w ≤ 100) a와 b는 간선을 나타내고, w는 그 간선의 가중치이다.
입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 모든 정점과 중앙 정점 사이의 비용의 합을 출력한다.

예제 입력 1 복사

5
0 1 2
1 2 1
1 3 7
3 4 5
6
0 1 1
1 2 4
2 3 1
3 4 4
4 5 1
0

예제 출력 1 복사

22
21

풀이정보

유형 : #DFS #DP #AD-HOC
참고 : https://www.crocus.co.kr/699
기여도 : 10%
풀이횟수 : 1
비고 :

• 8월 8일 SW검정 시험을 보고 난 후, 동일한 유형의 문제를 풀어봄.

  소스 (정답) - 20200820

  package bj;

  import java.io.BufferedReader;
  import java.io.BufferedWriter;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.io.OutputStreamWriter;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.StringTokenizer;

  /*

  • [백준-7812] 중앙 트리

  • 유형 : DFS, DP?, AD-HOC

  • 자력풀이정도 : 10%

  • 참고 : https://www.crocus.co.kr/699

  • 기타 의견 :

  • • 8월 8일 SW검정 시험을 보고 난 후, 동일한 유형의 문제를 풀어봄.

  • */

    public class bj7812 {

     public static int N;
     public static List<int[]> adjList[];
     public static int[] cnt;
     public static long[] sum;
     public static long ans;
    
     public static void main(String[] args) throws NumberFormatException, IOException {
             // TODO Auto-generated method stub
             System.setIn(new FileInputStream("D://sample_input.txt"));
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
             while(true){
    
                     N = Integer.parseInt(br.readLine().trim());
    
                     if(N == 0) {
                             break;
                     }
    
                     cnt = new int[N];
                     sum = new long[N];
    
                     adjList = new ArrayList[N];
                     for(int i=0; i<N; i++) {
                             adjList[i] = new ArrayList<int[]>();
                     }
    
                     for(int i=0; i<N-1; i++) {
                             StringTokenizer st = new StringTokenizer(br.readLine().trim());
                             int a = Integer.parseInt(st.nextToken());
                             int b = Integer.parseInt(st.nextToken());
                             int w = Integer.parseInt(st.nextToken());
                             adjList[a].add(new int[] {b,w});
                             adjList[b].add(new int[] {a,w});
                     }
    
                     ans = Long.MAX_VALUE;
                     getTree(0, -1);
                     getSum(0, -1, sum[0]);
    
                     bw.flush();
                     bw.write(ans + "\n");
             }
             bw.close();
    
     }
    
     public static void getTree(int here, int prev) {
             cnt[here] = 1;
    
             for(int i=0; i<adjList[here].size(); i++) {
                     int next = adjList[here].get(i)[0];
                     int cost = adjList[here].get(i)[1];
    
                     if(next == prev) {
                             continue;
                     }
    
                     getTree(next, here);
    
                     cnt[here] += cnt[next];
                     sum[here] += cost * cnt[next] + sum[next];
    
             }
     }
    
     public static void getSum(int here, int prev, long total) {
    
             ans = Math.min(ans, total);
    
             for(int i=0; i<adjList[here].size(); i++) {
                     int next = adjList[here].get(i)[0];
                     int cost = adjList[here].get(i)[1];
    
                     if(next == prev) {
                             continue;
                     }
    
                     getSum(next, here, total - (cnt[next]*cost) + ((N-cnt[next])*cost));
             }
    
     }

}

풀이

DFS 2번으로 풀 수 있는 문제이다.
사내 시험에 나온 문제 유형이다. 시험장에서 모든 정점에서 DFS를 돌리려고 하다가 시간초과가 났다.
자신을 포함한 하위 노드 수와 비용의 합을 구해두는 점에서 접근법은 맞았던 것 같다. 그런데 그것들을 3차원 배열에 담아둔 점과 DFS를 모든 정점에서 돌리려고 했던 점이 실패 요인이었다.
3차원 배열에 넣어두려고 했던 이유는 하위 노드의 수와 비용의 합을 구할때 방향성이 필요했기 때문이다. 그래서 모든 노드의 방향성마다 값을 저장하려고 했다.
결론적으로 그럴 필요가 없었다. 하나의 점을 루트로 지정하고 트리를 한번만 만들면 전부 구할 수 있었기 때문에, 한 방향만 고려하면 되었기 때문이다.

1. 0번 노드를 루트로 삼고, DFS를 수행한다. 루트는 꼭 0번일 필요는 없다.
2. DFS를 수행하면서, 자신을 포함한 하위 노드의 개수와 비용의 합을 구한다. 소스에서 보는 것 처럼 DFS 함수의 리턴값을 사용하지 않아도 저렇게 간단하게 구현이 가능하다. (실제 시험에서는 리턴을 받아서 처리했다. 그래도 상관은 없을 것 같다.)
3. 두번째 DFS를 수행하면서 모든 노드로의 비용의 합을 구한다.
   1. 0 → 1번 노드로 가는 기존 비용을 모두 삭제한다.
   2. 1번 → 0번 노드로 가는 비용을 추가한다.
   3. 1번노드 하위의 모든 노드까지의 비용의 합이 이미 저장되어 있기 때문에 거기서 a를 빼고 b를 더한다. 그러면 결국 b에서 모든 노드로 가는 비용을 알 수 있다. 이 과정을 DFS를 통해 모든 노드에서 반복한다.

회고

절반은 접근에 성공했지만 DFS 두 번에 전부 구할 수 있다는 생각은 왜 하지 못했을까? 공부를 더 많이 하면 과연 발상을 할 수 있었을지 의문이다.