백준 19535: ㄷㄷㄷㅈ

https://www.acmicpc.net/problem/19535

 

이 문제는 풀이가 꽤 재미있었던 문제였다.

단순히 그림을 그대로 받아들였을 때엔 풀이법을 떠올리기 어려웠다.

하지만, "ㄷ"과 "ㅈ"의 조건을 생각으로 옮기니 어느정도 해결책을 떠올리기 시작했다.

 

단순하게 생각을 하면된다.

"ㄷ"은 트리내에서 이어진 노드 4개의 갯수를 찾으면 된다.

"ㅈ"은 힌 노드와 이어지는 노드의 갯수가 3개 이상인것들을 찾으면 된다.

 

여기서 "ㅈ"의 갯수는 금방 계산할 수 있다.

모든 노드를 돌며 연결된 노드 갯수가 3개 이상일 때, 그 노드들을 3개 씩 고르는 가짓수를 구하면 된다.

즉, 조합을 사용하면 _{이어진 노드 갯수} C ₃  이렇게 구할 수 있다. 그렇게 모든 노드에서 각각 계산해서 더한다.

 

문제는 "ㄷ"이였다. 단순하게 계산하면, dfs로 구할 수 있을 것 같은데, 이 방식으론 "시간 초과"가 날 것 같았다.

혹시나 한 번 dfs로 계산을 시도했지만

ll dfs(int here, int d, int p)
{
	if (d == 3) return 1;
	ll ret = 0;
	for (int i = 0; i < adj[here].size(); i++)
		if (adj[here][i] != p)
			ret += dfs(adj[here][i], d + 1, here);
	return ret;
}

역시나 시간 초과가 되었다. 

그렇다면, 시점을 달리하면 된다. 이 방식은 꼭짓점 노드를 중심으로 계산하는 식인데, 중간 노드를 기준으로 생각을 하면 어떨까?

 

이어진 노드 한 쌍을 골랐을 때, 한 쪽에서 연결된 노드 갯수와 다른 한 쪽에서 연결된 노드 갯수로 "ㄷ"을 구할 수 있다.

이어진 노드 하나를 빼는 것도 잊지 말자.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
using ll = long long;
vector<int> adj[300001];
ll v[300001][4];
int N, U, V;
ll D = 0, G = 0;
string ans = "DUDUDUNGA";

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(v, -1, sizeof(v));
	cin >> N;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> U >> V;
		adj[U].push_back(V);
		adj[V].push_back(U);
	}
	for (int here = 1; here <= N; here++)
	{
		ll s = adj[here].size();
		if (s >= 3)
			G += (s * (s - 1) * (s - 2)) / 6;
		if (s >= 2)
		{
			for (int& there : adj[here])
				if (adj[there].size() >= 2)
					D += (s - 1) * (adj[there].size() - 1);
		}
		
	}
	D /= 2;
	if (D < 3 * G) ans = "G";
	if (D > 3 * G) ans = "D";
	cout << ans << '\n';
}

처음 마주했을 땐 답답했던 문제였지만, 이렇게 생각을 하니 재밌는 문제가 되었다.