백준 19535 <ㄷㄷㄷㅈ>

문제에서부터 이해도가 필요한 문제이다 골드 3이라고 하지만 골드 1 수준이라고 느껴질 만큼 어려웠던 문제이다.

 

이 문제를 풀면서 다시 한번 중요하게 생각했던 것은 범위를 확실하게 봐야 한다는 것이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

다음은 ㄷ의 경우를 고려해보자. ㄷ의 경우는 어떤 점과 어떤 점이 연결되어 있을 경우 각각의 점에서 다른 점에 연결될 수 있는 경우들을 고려해주면 된다. 

이렇게 기본적인 이해를 하고 난 뒤 다음 문제를 풀 수 있다. 물론 ㅈ같은 경우는 자신이 연결되어 있는 개수만 알면 되지만 ㄷ같은 경우는 어떻게 처리를 해야 될지에 대해 많은 고려사항이 있었다.

 

그래서 선택한 방법이 다음 이동할 노드와 이전 노드를 동시에 큐에 담는 것이 좋다고 생각했다. 

 

bfs를 할 때 시작점을 큐에 넣어줄 때 이전 노드가 존재하지 않기 때문에 -1을 x좌표에 1을 y좌표에 넣어 x좌표를 이전 좌표 y좌표를 현재 좌표로 나타내 동시에 Point로 받아서 큐에 저장해서 x좌표가 -1이 아닐 때에만 ㄷ의 경우를 계산해주도록 처리를 했다.

 

 

BFS를 돌리면서 d값과 g값에 값을 넣는 경우가 이문제에서 가장 애를 먹었던 부분이다 ㅠㅠ

 

범위가 처음부터 30만 이기 때문에 long값이 나올 수도 있다는 것을 고려하지 않아... 많은 실패가 발생했다.

이런 초보적인 실수를 하다니 ㅠㅠ

알고리즘은 잘 구성했지만 이런 문제에 있어 집중을 가지고 살펴봐야 한다는 걸 다시 깨달았다..

 

전체 코드

import java.awt.Point;
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 Main{

	static int n, visit[];
	static long d,g;
	static ArrayList<Integer> a[];
	static Queue<Point> q;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(kb.readLine());
		a = new ArrayList[n + 1];
		visit = new int[n + 1];
		q = new LinkedList<Point>();
		for (int i = 0; i <= n; i++) {
			a[i] = new ArrayList<Integer>();
		}
		for (int i = 1; i < n; i++) {
			StringTokenizer st = new StringTokenizer(kb.readLine());
			int f = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			a[f].add(s);
			a[s].add(f);
		}
		visit[1] = 1;
		q.add(new Point(-1, 1));
		bfs();

		if (d == g * 3) {
			System.out.println("DUDUDUNGA");
		} else if (d > g * 3) {
			System.out.println("D");
		} else {
			System.out.println("G");
		}

	}

	public static void bfs() {
		while (!q.isEmpty()) {
			Point next = q.remove();
			for (int i = 0; i < a[next.y].size(); i++) {
				if (visit[a[next.y].get(i)] == 0) {
					visit[a[next.y].get(i)] = 1;
					q.add(new Point(next.y, a[next.y].get(i)));
				}
			}
			if (next.x != -1) {
				long f=a[next.x].size() - 1;
				long s=a[next.y].size() - 1;
				d += (f*s);
			}
			if (a[next.y].size() >= 3) {
				long f=a[next.y].size();
				long s=a[next.y].size() - 1;
				long t=a[next.y].size() - 2;
				long mi=6;
				g += ((f*s*t)/mi);
			}
		}
	}
}