[BOJ] 20647. Cowntagion (Graph)

#. Problem

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

* The copyright in this matter is in acmicpc

 

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

농장 : 1 ~ N^5
길 : 1 ~ N-1

 

<주어진 정보>
이벤트
1. 해당 농장에서 감염 소 2배 증가
2. 감염된 소 한 마리가 인접 농장으로 이동

 

<목적>
"모든 농장에서 적어도 한 마리의 소가 질병에 걸리기까지 가능한 최소 일수"

 

//

 

오랜만에 푸니까 적응이 안 되는군...

 

우선 N은 최대 10^5 이므로, 한 번의 반복문에서 끝내야 한다.

처음에 그래프 문제라고 생각은 해서 단순하게 풀어보려고 단방향으로만 생각을 했었다. 
하지만.. 단방향으로 풀게 되면 루트(부모 노드)를 찾을 수 없게 되었고..
결국 양방향으로 전환을 해서 트리 모양을 만들어 풀게 되었다.

#. Code

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    FastScanner in;
    PrintWriter out;
    
    static int N, a, b, cntAdjacentLoads[];
    void solve() {
        N = in.nextInt();
        cntAdjacentLoads = new int[N + 1];
        
        for (int i = 0; i < N-1; i++) {
            a = in.nextInt();
            b = in.nextInt();
            cntAdjacentLoads[a]++;
            cntAdjacentLoads[b]++;
        }
 
        int day = 0;
        for (int i = 1; i <= N; i++) {
            if (cntAdjacentLoads[i] > 1) { // 연결된 길이 있을 경우 (자식 노드가 있을 경우)
                if (i != 1) cntAdjacentLoads[i]--; // 부모 노드는 이미 방문하였으므로 제외 (root 노드는 부모 노드가 없으므로 pass)
                int infectedCow = 1; // 감염된 소
                while (infectedCow < cntAdjacentLoads[i] + 1) { // 연결된 농장의 개수(+1은 현재 농장)만큼 감염된 소 증가
                    infectedCow *= 2; // 해당 농장에서 감염 소 2배 증가
                    ++day;
                }
            } 
 
            if (i != 1) day++; // 감염된 소 한 마리가 인접 농장으로 이동하는 이벤트
        }
        
        out.println(day);
    }
 
    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
 
    public static void main(String[] args) {
        new Main().run();
    }
 
    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
 
        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
 
        long nextLong() {
            return Long.parseLong(nextToken());
        }
 
        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}