[PS]#The Story of a Tree

 

 

---

 

https://www.hackerrank.com/challenges/the-story-of-a-tree/problem?isFullScreen=true

The Story of a Tree | HackerRank

 

#include <bits/stdc++.h> 
using namespace std; 
#define PII pair<int, int> 
int q, n, g, k, Count[100001]; 
bool visit[100001]; 
set<string> gmap;

int DFS(vector<vector<int>>& grid, int x) 
{ 
	if (visit[x]) return 0; 
	visit[x] = true; 
	int res = 0; 
	for (int i = 0; i < grid[x].size(); ++i) 
	{ 
		if (visit[grid[x][i]]) continue; 
		string str = to_string(x) + to_string(grid[x][i]); 
		if (gmap.find(str) != gmap.end()) ++res; 
		res += DFS(grid, grid[x][i]); 
	} 
	return res; 
}

void LoopDFS(vector<vector<int>>& grid, int idx, int beforeIdx, int cnt) 
{ 
	if (visit[idx]) return; 
	visit[idx] = true; 
	int curCnt = cnt; 
	if (beforeIdx != -1) 
	{ 
		string beforeStr = to_string(beforeIdx) + to_string(idx); 
		string Str = to_string(idx) + to_string(beforeIdx); 
		if (gmap.find(beforeStr) != gmap.end()) curCnt--; 
		if (gmap.find(Str) != gmap.end()) curCnt++; 
	} 
	Count[idx] = curCnt; 
	for (int i = 0; i < grid[idx].size(); ++i) 
	{ 
		if (visit[grid[idx][i]]) continue; 
		LoopDFS(grid, grid[idx][i], idx, curCnt); 
	} 
}

PII Calc(int x, int y) 
{ 
	int X = x, Y = y; 
	for (int i = 2; i <= X;) 
	{ 
		if (X % i == 0 && Y % i == 0) 
		{ 
			X /= i; Y /= i; 
			i = 2; 
		} 
		else ++i; 
	} 
	return PII(X, Y); 
}

string storyOfATree(vector<vector<int>> edges, vector<PII> guesses) 
{ 
	vector<vector<int>> grid(n + 1); 
	for (int j = 1; j <= n; ++j) 
	{ 
		for (int i = 0; i < edges[j].size(); ++i) 
		{ 
			grid[j].push_back(edges[j][i]); 
			grid[edges[j][i]].push_back(j); 
		} 
	} 
    
	gmap.clear(); 
	int gsz = guesses.size(); 
	for (int i = 0; i < gsz; ++i) 
	{ 
		int f = guesses[i].first, s = guesses[i].second; 
		string str = to_string(f) + to_string(s); 
		gmap.insert(str); 
	} 
    
	memset(visit, false, sizeof(visit)); 
	int initCnt = DFS(grid, 1); 
    
	memset(visit, false, sizeof(visit)); 
	memset(Count, 0, sizeof(Count)); 
	LoopDFS(grid, 1, -1, initCnt); 
    
	int answer = 0; 
	for (int i = 1; i <= n; ++i) 
	{ 
		if (Count[i] >= k) ++answer; 
	} 
    
	PII cc = Calc(answer, n); 
	if (cc.first == 0) cc.second = 1; 
	string answerStr = to_string(cc.first); 
	answerStr.append("/"); 
	answerStr += to_string(cc.second); 
	return answerStr; 
}

 

* 문제 풀이 과정

 

문제를 간단히 요약하자면,

모든 노드는 루트가 될 수 있다.

임의의 노드가 루트일 때, 주어진 데이터 guesses 를 만족하는 경로의 갯수를 point 라고 한다.

k >= point 라면 해당 노드는 참.

( 참이 되는 노드의 수 / 모든 노드의 수 ) 인 값을 문자로 출력하자.

 

모든 경우의 수를 찾는 것은 어렵지 않다.

DFS 를 이용해 모든 노드를 돌아가며 Alice 가 추측한 guesses 벡터에 포함된 경로가 존재하는지 확인할 수 있다.

 

문제는 '시간 초과' 이다. 어떻게 줄일 수 있을까 ??

시간 초과 문제에서 중요하게 볼 요점은 논리적으로 순서를 바꾸거나 조합하는 것이 아니라

등장하는 주요 for 문을 어떤 알고리즘이나 방식으로 없애거나 줄여야만 한다.

로직을 아예 바꾸어야한다는 것을 인지해야한다.

 

다른 말로 하면 안타깝게도 시간 초과 문제는

요약할 수 있는 방식을 못 찾으면 풀지 못한다.

 

하지만 풀어야만 하는 상황에서 우리는 어디서 단서를 찾을 수 있을까 ??

우선, 주어진 데이터를 보아야한다.

또, 우리가 출력해야하는 결과 값에 필요한 과정들을 파악해야한다.

 

이 문제를 빗대어 살펴보자.

 

주어진 데이터 : 양방향 경로가 담긴 데이터, 방향을 예측하는 Alice 의 추측 데이터.

결과 값에 필요한 요소 : 모든 노드가 루트인 경우마다 Alice 추측한 데이터 확인.

( 모든 노드는 서로 연결되어 있다. )

 

1. 모든 경로를 돈다. (for)

1. DFS 를 통해 해당 경로를 확인하고 계산. ( for )

=> 중첩 for 문. (총 n 제곱, O(n2) )

 

위를 토대로,

DFS 로 모든 노드를 거치면서 루트로 설정할 수 있는 것과

이전 노드가 루트인 상황에서 현재 노드가 루트인 상황으로 올 때의 차이점만 구별한다면

모든 경로를 도는 for 문을 지울 수 있는 사실을 알아내야만 한다.

 

 

정리하면,

DFS 로 들어간 상황의 idx 가 root 가 된다.

이전의 idx, 지금의 idx 를 비교하며

루트가 바뀌어 세어야할 경로가 없어지는 경우, 경로가 새로 생기는 경우를 고려한다.

 

1. 임의의 노드를 기준으로 ( 코드에서는 '1' 노드 ) 초기의 값 ( Alice 의 예측이 맞은 총 갯수 )을 구한다.

2. DFS 에 idx, 이전의 idx, 초기의 값을 파라미터로 돌리면서 앞서 말한 경루를 고려해 값을 구해나간다.

=> 중첩이 아니다. ( O(n) )

 

추가적으로,

노드 n 의 개수가 너무 많기 때문에 배열 인덱스를 이용해서 ( O(1) ) 해당 연결 여부를 찾을 수 없다.

string 을 키로 하는 set 컨테이너를 이용해서 O( log(n) ) 으로 찾게 구현하였다.

 

마지막으로 값을 출력할 때,

분자, 분모가 서로 약분될 수 있으므로 Calc 함수를 구현해 따로 계산해주었다.

 

 

 

 

* 해결 과정 문제점

 

시간 초과를 해결할 수 있는 방법을 찾지 못해 시간이 많이 소모됐다.

계속 시간 복잡도가 같은 방식으로만 로직을 바꾼 것이 큰 요인으로 보인다.

 

 

 

 

 

 

* 또 다른 해결 방법

 

서로 약분되어질 최대공약수를 구하는 gcd 방법을 이용하는 것.

 

int GCD(int a, int b)
{
	if (b == 0) return a;
	return GCD(b, a % b);
}