96. ㄷㄷㄷㅈ (백준 19535)

 

문제

문제 링크 : https://www.acmicpc.net/problem/19535

19535번: ㄷㄷㄷㅈ

문제

어느 날, 트리를 물끄러미 보고 있던 동현이는 엄청난 사실을 하나 발견했다. 바로 정점이 네 개인 트리는 ‘ㄷ’과 ‘ㅈ’의 두 종류밖에 없다는 사실이다!

정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자.

이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다.

• D-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 많은 트리
• G-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 적은 트리
• DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 3배만큼 있는 트리

신이 난 동현이는 트리만 보이면 그 트리에 있는 ‘ㄷ’과 ‘ㅈ’이 몇 개인지 세고 다니기 시작했다. 하지만 곧 정점이 30만 개나 있는 트리가 동현이 앞에 나타났고, 동현이는 그만 정신을 잃고 말았다. 동현이를 대신해 주어진 트리가 D-트리인지 G-트리인지 아니면 DUDUDUNGA-트리인지 알려주자!

입력

첫 번째 줄에 트리의 정점 수 N이 주어진다. (4≤N≤300 000)

두 번째 줄부터 N−1개의 줄에 트리의 각 간선이 잇는 두 정점의 번호 u, v가 주어진다. (1≤u,v≤N)

출력

첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다.

 

풀이

우선 정점이 30만개이기 때문에, 모든 조합을 만들어서 확인하는건 힘들다.

그래서 생각한게 중복없이 아래로 내려가서 체크하는 방법이다.

D를 잘 보면 순서대로 부모라고 했을때 1:2:1, 1:1:1:1이고,

G는 1:3, 1:1:2 두가지 경우가 존재한다.

 

여기서 당연하게 입력받은 노드가 부모-자식 순일거라고 생각했지만, 사실은 뒤죽박죽이다.

따라서 뭐가 루트, 부모인지 모르기 때문에 사실상 얘를 트리 풀듯이 접근하면 힘들었었다.

그냥 노드 하나랑, 거기 붙어있는 사이클이 없는 그래프라고 생각해보자.

G는 그럼 결국 노드 하나에 붙어있는 다른 노드들의 수 (n) C 3이된다.

D는 그래프를 좀 돌려서 생각해보면, 가운데 낀 a - b에 각각 달려있는 나머지 애들을 곱해준 형태가 된다.

따라서 각 노드에 딸려 있는 나머지 노드들을 곱해주면 된다.

 

여기서 D를 BFS를 사용해서 한 쌍 씩 탐색해가면서 구할 수 있는데, 더 간단하게 할 방법이 있다.

G는 nC3만 해주면 되기 때문에, n만 저장하면 구할 수 있다.

D는 결국 노드 2쌍마다 연결된 나머지 노드들을 구해주는 건데, 노드 2쌍이 곧 간선이기 때문에 모든 간선을 탐색하면 된다.

어차피 모든 간선은 문제에서 입력값으로 주기 때문에, 각각의 노드에 연결된 다른 노드의 숫자만 저장하면

애초부터 문제에서 그래프를 저장할 필요가 없게 된다.

그럼 결국 문제에서 입력받은 각 간선들에 대해 D를 구해주면, D도 간단하게 구할 수 있다.

 

이때 총 노드가 30만개이기 때문에 int형으로는 범위가 초과될 수 있다!!!!!!!!!!!

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.awt.Point;

public class Main {

    //정점 30만 -> 4개 뽑아서 저장 불가능. (조합확인 힘듦)
    //아래로 내려가면서 중복없이 체크하기 -> 근데 누가 루트인지 알 수 없음. (입력 순서가 부모-자식이 아님)
    //-> 연결리스트 그래프로 접근
    //D -> 1:2:1 or 1:1:1:1 => nC2 + 4자식 => 부모-자식에서 각각 나머지애들 곱
    //G -> 1:3 or 1:1:2 => nC3 + nC2 => n+1(부모포함)C3
    //-> 어차피 G는 모든 노드들 곱으로 계산가능
    //-> 각각 노드의 입력을 Q에 저장하면 중복되는 부모-자식 없음 -> 바로 D도 계산 가능
    //30만이라 long으로 하기

    static int N;
    static long D = 0;
    static long G = 0;

    static long[] nodes;
    static Queue<Point> q;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        nodes = new long[N+1];
        q = new LinkedList<>();

        int parent, child;

        for(int i=0; i<N-1; i++){
            st = new StringTokenizer(br.readLine());
            //왼쪽이 무조건 부모인게 아님!!!!!!!!!!!!
            parent = Integer.parseInt(st.nextToken());
            child = Integer.parseInt(st.nextToken());

            nodes[parent]++;
            nodes[child]++;

            q.add(new Point(parent, child));
        }
        calG();
        calD();
        output();
    }

    public static void calG(){
        for(int i=1; i<N+1; i++){
            if(nodes[i] >= 3){
                G = G + (nodes[i] * (nodes[i] -1) * (nodes[i]-2)) / 6 ;
            }
        }
    }

    public static void calD(){
        while (!q.isEmpty()){
            Point cur = q.poll();
            D = D + (nodes[cur.x]-1) * (nodes[cur.y]-1);
        }
    }


    public static void output(){
        if(D > G*3){
            System.out.println("D");
        }
        else if (D < G*3){
            System.out.println("G");
        }
        else{
            System.out.println("DUDUDUNGA");
        }
    }
}

 

결과