[BOJ] 백준 19535번 ㄷㄷㄷㅈ (Java)

#19535 ㄷㄷㄷㅈ

난이도 :  골드 3

유형 : 트리 / 조합론 

19535번: ㄷㄷㄷㅈ

▸ 문제

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

 

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

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

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

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

▸ 입력

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

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

▸ 출력

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

 

 

문제 풀이  

그냥 DFS로 풀리는 문제인 줄 알았지만 아니었다. 노드의 갯수가 최대 30만개로 DFS탐색으로 모든 노드를 조회하면 시간초과가 발생한다. 'ㄷ'를 만족하는 트리와 'ㅈ'을 만족하는 트리의 규칙을 찾아내서 연산과정을 줄여줘야 한다.

 

'ㄷ'를 만족하는 트리

각 정점의 관계를 살펴보면 간선의 갯수는 1, 2, 2, 1이다. 끝 머리에 있는 노드는 어떤 노드여도 상관없고 가운데에 껴있는 두 정점이 'ㄷ'트리를 만드는 중요 부분이다. 다음 그림과 같이 가운데 두 정점과 연결되어 있는 끝의 간선의 갯수를 통해 'ㄷ'트리의 갯수를 세어볼 수 있다. 왼쪽 빨간색의 한 노드와 오른쪽 파란색의 한 노드를 연결지으면 총 6가지의 'ㄷ'트리가 나온다.

 

'ㄷ' 트리

'ㅈ'를 만족하는 트리

'ㅈ'트리를 찾는 방법은 더 쉽다. 간선의 갯수가 3개 이상인 노드를 찾은 다음 중복되는 트리를 제거해주면 된다. 연결되어 있는 n개의 노드 중 3개를 선택하면 되므로 조합을 사용하여 nC3을 구해주면 된다.

 

'ㅈ' 트리

 

설계

1. 주어진 노드를 인접리스트 배열에 저장한다.
2. 모든 노드를 순차 탐색한다.  for i : 1~n
   1. 간선의 갯수(a)가 3개 이상인 노드는 'ㅈ'트리가 될 수 있으므로 aC3의 값을 구해준다.
      1. g += (a*(a-1)*(a-2))/6;
   2. i번 노드와 연결되어 있는 nxt노드 끝에 연결되어 있는 간선의 갯수를 통해 'ㄷ'트리의 갯수를 구해준다.
      1. d += (a-1)*(b-1);

 

풀이 코드 

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

public class Main {

	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		StringTokenizer st;
		for(int i=0; i<n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			list[u].add(v);
			list[v].add(u);
		}
		
		long d =0, g=0;
		boolean[] check = new boolean[n+1];
		for(int i=1; i<n+1; i++) {
			long a = list[i].size();
			if(a >= 3) {
				g += (a*(a-1)*(a-2))/6;
			}
			
			check[i] = true;
			for(int nxt : list[i]) {
				long b = list[nxt].size();
				if(!check[nxt]) {
					d += (a-1)*(b-1);
				}
			}
		}
		
		if(d > 3*g) {
			System.out.println("D");
		}else if(d < 3*g) {
			System.out.println("G");
		}else {
			System.out.println("DUDUDUNGA");
		}
	}
}