[백준] 알고리즘 분류(트리,JAVA)19535번, ㄷㄷㄷㅈ

문제 링크

19535번: ㄷㄷㄷㅈ

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 트리에서 4점을 이용하여 만들 수 있는 모양은 'ㄷ',  'ㅈ'만 존재한다.

2. 주어진 트리에서 'ㄷ'의 개수와 'ㅈ'의 개수에 따른 결과를 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 노드에 연결된 다른 노드의 개수를 이용하여 'ㄷ', 'ㅈ'의 개수를 구합니다.

 

3. 'ㄷ', 'ㅈ'의 개수에 따른 결과를 출력합니다.

 

'ㄷ' 모양.

 

DFS를 통해서 연결된 간선이 3개인지 확인할 수도 있지만 '시간초과'가 발생합니다.

 

각 연결된 노드에서 'ㄷ'를 만들 수 있는 개수를 모두 구해서 더하였습니다.

빨간구역의 노드가 연결되었으면

위쪽 노드는 주황색

아래쪽 노드는 파란색

한 번더 이동이 가능하기 때문에 'ㄷ'모양을 만들 수 있습니다.

빨간구역의 노드가 연결되었으면

위쪽 노드는 주황색

아래쪽 노드는 파란색

파란색은 이동이 더 불가능하기 때문에 'ㄷ'모양을 만들 수 있습니다.

다른 모양으로 살펴보면

빨간구역의 노드가 연결되었으면

위쪽 노드는 주황색

아래쪽 노드는 파란색

한 번더 이동이 가능하기 때문에 'ㄷ'모양을 만들 수 있습니다.

'ㄷ'모양을 만들 수 있는 개수는 : 3 × 2 = 6개

 

이를 통해 점화식을 구하실 수 있습니다.

점화식 : (노드1의 연결된 노드 개수 - 1) × (노드2의 연결된 노드 개수 - 1)

※ -1을 하는 이유는 연결된 노드에는 노드1이나 노드2가 포함되어있기 때문입니다.

 

위에 모양에 적용시켜보면

(주황색의 연결된 노드 개수 - 1) × (파란색의 연결된 노드 개수 - 1)

(4 - 1) × (3 - 1) = 3 × 2 = 6

 

'ㅈ' 모양.

하나의 노드에서 연결된 노드의 3개를 선택할 때 'ㅈ'모양을 만들 수 있습니다.

연결된 노드가 4개이면 3개를 선택할 수 있는 경우는 4개(빨, 파, 초, 주)가 됩니다.

4개중 3개를 선택한다는 것은 조합을 이용한다는 것으로 아래의 식을 사용한 것입니다.

 

nC₃ = n! / (n-3)! × 3!

 

n!에서 (n-3)!을 약분하면n! = n × (n-1) × (n-2) × (n-3) × (n-4) × .... × 1

 

(n-3)! = (n-3) × (n-4) × .... × 1

 

식을 약분한뒤 표현

nC₃ = n × (n-1) × (n-2) / 6(3!)

 

₄C₃ = 4 × 3 × 2 / 6 = 4

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

N : 6

노드	연결된 노드 개수
1	1
2	1
3	1
4	3
5	1
6	1

 

2. 각 노드에 연결된 다른 노드의 개수를 이용하여 'ㄷ', 'ㅈ'의 개수를 구합니다.

 

'ㄷ'의 개수.

(2 - 1) × (2 - 1) = 1개

 

(2 - 1) × (3 - 1) = 2개

 

'ㅈ'의 개수.

₃C₃ = 3 × 2 × 1 / 6 = 1개

 

3. 'ㄷ', 'ㅈ'의 개수에 따른 결과를 출력합니다.

 

'ㄷ'의 개수 : 3개

'ㅈ'의 개수 : 1개

'ㅈ'의 개수를 3배하였을 때 'ㄷ'의 개수와 같기 때문에

"DUDUDUNGA" 결과로 출력됩니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 트리의 정보를 띄어쓰기 기준 나누었습니다.
• 각 노드가 다른 노드와 연결된 개수를 가지고 DCal, GCal을 사용하여 'ㄷ', 'ㅈ'의 개수를 구합니다.
• 'ㄷ', 'ㅈ'의 개수에 따른 결과를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• DCal함수는 간선에 대한 점화식을 적용하여 'ㄷ'모양의 개수를 구합니다.
• GCal함수는 연결된 다른 노드 개수와 점화식을 이용하여 'ㅈ'모양의 개수를 구합니다.

 

import java.awt.*;
import java.io.*;
import java.util.*;


public class Main {
    static int N;
    static long D=0, G=0;	//ㄷ, ㅈ 모양 개수
    static int[] child;	//연결된 노드 개수 저장 배열
    static ArrayList<Point> line = new ArrayList<>();	//간선 정보 저장 리스트
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        child = new int[N+1];
        //트리의 정보 저장
        for(int i=1;i<N;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            child[u]++;	//연결된 노드 +1
            child[v]++;	//연결된 노드 +1
            line.add(new Point(u, v));	//간선 추가
        }
        //ㅈ모양 개수 구하기.
        for(int i=1;i<=N;i++){
            if(child[i] >= 3)	//연결된 노드가 3개 이상이어야 ㅈ모양 가능
                G += GCal(child[i]);
        }
        //ㄷ모양 개수 구하기
        DCal();
        //ㄷ개수가 ㅈ개수의 3배보다 많을 때
        if(D > G * 3)
            bw.write("D");
        else if(D < G * 3)	//ㄷ개수가 ㅈ개수의 3배보다 적을 때
            bw.write("G");
        else	//ㄷ개수가 ㅈ개수의 3배와 같을 때
            bw.write("DUDUDUNGA");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //모든 간선에 대하여 ㄷ개수 구하는 점화식 진행하는 함수
    static void DCal(){
        for(Point cur : line)
            D += (child[cur.x] - 1) *(long)(child[cur.y] - 1);
    }
    //ㅈ개수 구하는 점화식 진행하는 함수
    static long GCal(int n){
        return (long)n * (n-1) * (n-2) / 6;
    }
}