[BOJ] 19535.ㄷㄷㄷㅈ(그래프).java

#. Problem

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

* The copyright in this matter is in BOJ

#. 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

  

'ㅈ' Tree는 특정 노드의 간선 개수 조합으로 쉽게 찾을 수 있다.

간선 세 개로 'ㅈ' Tree가 완성되므로 아래와 같은 식을 얻을 수 있다.

N개의 간선 중 3개를 뽑는 경우의 수

nC3 = n! / 3!(n-3)! = n*(n-1)*(n-2) / 3 * 2 * 1

다음은 'ㄷ' Tree를 찾는 것인데,

처음에 DFS로 접근했더니 시간초과가 나버렸다.

최대 N이 300,000이라서 DFS로는 버거운 테스트 케이스가 있나보다ㅠㅠ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

private static void findDTree(int parent, int child, int cnt) {              // ㄷ Tree가 만들어졌을 경우 count     if(cnt == 3) {         // 시작점이었던 노드가 마지막지점이라면 pass         if(!isStart[child]) D++;         return;     }          for (int i = 0; i < tree[child].size(); i++) {         // 부모 노드일 경우 pass         if(tree[child].get(i) == parent) continue;         findDTree(child, tree[child].get(i), cnt + 1);     } }     Colored by Color Scripter

cs

그래서 생각한 다른 방법이

연결된 두 노드를 두고 'ㄷ'Tree를 찾는 방법이다.

아래 그림에서 빨간색으로 칠해진 연결된 두 노드로부터 만들어지는 'ㄷ'Tree 개수를 찾기 위해서는

(현재 노드의 간선 - 1) * (연결된 노드의 간선 - 1) 로 구할 수 있다.

-1을 해주는 이유는 연결된 간선은 제외하기 위해서다.

아래 그림을 예를 들어보면,

2 * 4 로 8개의 'ㄷ' Tree 를 만들 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ19535 {       static int N;     static long D, G;     static boolean[] checked;     static ArrayList<Integer>[] tree;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  N = Integer.parseInt(br.readLine());         tree = new ArrayList[N+1];         checked = new boolean[N+1];         for (int i = 1; i <= N; i++)              tree[i] = new ArrayList<>();                      for (int i = 0; i < N - 1; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());                          tree[a].add(b);             tree[b].add(a);         }           // ㅈ Tree 찾기         for (int i = 1; i <= N; i++) {             if(tree[i].size() >= 3) {                 // nC3 = n!/3!(n-3)! = n(n-1)(n-2) / 3 * 2                 long n = tree[i].size();                 G += (n * (n-1) * (n-2)) / 6;             }         }           // ㄷ Tree 찾기         for (int p = 1; p <= N; p++) {             long pChild = tree[p].size() - 1;                          for (int c = 0; c < tree[p].size(); c++) {                 // 이미 확인한 노드일 경우                 if(checked[tree[p].get(c)]) continue;                 // (현재 노드의 간선 - 1) * (연결된 노드의 간선 - 1)                  D += pChild * (tree[tree[p].get(c)].size() - 1);             }             // check!             checked[p] = true;         }           if(G * 3 < D) System.out.println("D");         else if(G * 3 > D) System.out.println("G");         else System.out.println("DUDUDUNGA");     }      }   Colored by Color Scripter

cs

#. Code_v2

문제의 특성을 이해했다면

이렇게 해결해볼 수 있다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ19535 {
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        long[] Edge = new long[N+1];
        long D = 0, G = 0; 
        
        Queue<Point> q = new LinkedList<>();
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            Edge[a]++; Edge[b]++;
            q.add(new Point(a, b));
        }
 
        // ㅈ Tree 찾기
        for (int i = 1; i <= N; i++) {
            if(Edge[i] >= 3) {
                // nC3 = n! / 3!(n-3)! = n(n-1)(n-2) / 3 * 2
                long n = Edge[i];
                G += (n * (n-1) * (n-2)) / (3 * 2);
            }
        }
 
        // ㄷ Tree 찾기
        while(!q.isEmpty()) {
            Point now = q.poll();
            D += (Edge[now.x] - 1) * (Edge[now.y] - 1);
        }
 
        if(G * 3 < D) System.out.println("D");
        else if(G * 3 > D) System.out.println("G");
        else System.out.println("DUDUDUNGA");
    }    
    
}