[백준] 19535 ㄷㄷㄷㅈ

1. 문제

2. 접근방법

ㄷㄷㄷㅈ 제목이 신난다.

 

정점 4개로 만들 수 있는 모양 ㄷ과 ㅈ에 관한 문제

정점의 갯수가 30만개 까지 나오니 모든 경우의수를 구해서 풀면 당연히 안된다.

그러니 다른 방법을 찾아보자

 

먼저 ㄷ이랑 ㅈ의 특징을 보면

ㄷ 친구는 선 2개짜리 2개 1개 짜리 2개 씩 있다.

 

 

 

ㅈ 친구는 선 3개 정점 하나랑 선 1개짜리 정점 3개가 있다.

 

 

 

 

 

ㅈ부터 살펴보면 한 정점을 중심으로 3개의 선을 선택 하면 되는데

D을 중심으로 보면

요렇게 4가지 경우가 나올 수 있다.

즉 D에 연결된 4개 중에서 3개를 고르는 NC3 의 갯수를 구하면 된다.

 

그 다음 ㄷ을 보면

연결된 정점의 수가 1 2 2 1 이니

 

D를 기준으로 봤을때

부모와 나를 선택하고

부모에서 한개 나에서 한개 씩 고르면 된다.

즉 (부모한테 연결된것 -1) * (나한테 연결된것 -1)를 하면 한 정점에서의 ㄷ 갯수를 구할 수 있다.

 

3. 풀이

1. 정점의 갯수를 입력받고 각 부모를 저장할 list(parents)와 각 정점에 연결된 정점의 수를 저장할 list(lineNum) 생성

2. 입력 받은 간선배열에서 양쪽 정점의 lineNum에 +1

3. 간선배열은 부모 자식 짝 맞추기 위해 인접리스트에 저장 해 두었다가

4. bfs를 돌며 부모 자식 짝 맞추기

5. 이제 각 정점에 대해 ㅈ의 갯수는 N C 3으로 ㄷ의 갯수는 (부모의 갯수 - 1) * (자식의 갯수 -1) 로 구해 총 ㄷ의 갯수와 ㅈ의 갯수 세기

6. 각 상황에 맞는 D , G , DUDUDUNGA 출력

 

 

4. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P19535ㄷㄷㄷㅈ {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int parents [] = new int [N+1];
		int lineNum [] = new int [N+1];
		ArrayList<Integer>[] list = new ArrayList[N+1];
		for(int i = 0 ; i < N+1 ; i++)
			list[i] = new ArrayList<Integer>(); //부모 자식 짝맞추기 용
		
		for(int i = 0 ; i < N+1 ; i++)parents[i] = i;
		
		for(int i = 0 ; i < N-1 ; i++) {
			st= new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			list[start].add(end);
			list[end].add(start);
			parents[end] = start;
			lineNum[start]++;
			lineNum[end]++;
		}
		
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(1);
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i = 0 ; i < list[now].size(); i++) {
				int target = list[now].get(i);
				if(parents[now] == target)
					continue;
				parents[target] = now;
				que.offer(target);
			}
		}
		
		
		
		long E = 0; //ㄷ
		long W = 0; //ㅈ
		for(int i = 1 ; i < N+1 ; i++) {
			long myNum = lineNum[i];
			long parentNum = lineNum[parents[i]]; 
			if(myNum >= 3 ) W += myNum*(myNum-1)*(myNum-2)/1/2/3;
			if(parents[i] != i)E += (myNum-1) * (parentNum -1);
		}
		
		String result = "";
		if(E > W*3)result = "D";
		else if(E == W*3)result = "DUDUDUNGA";
		else if(E < W*3)result = "G";
		System.out.println(E+ " " + W);
		System.out.println(result);
	}

}

5. 마치며

처음에 테케는 맞는데 틀렸습니다가 떠서 왜 그런지 보니

그래프에서 숫자가 작을 수록 rank가 당연히 낮겠지 생각하고 부모자식을 이어줬던게 문제였다.

다시 인접리스트로 받아서 제대로 짝지어주니 바로 통과 되었다.