BOJ #15681. 트리와 쿼리 (Silver 상위권)

오늘은 그래프와 dp를 모두 좋아하시는 분이라면 아주 신이 날 문제(...)를 리뷰하게 됐습니다!

www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

바로 백준 15681번. 트리와 쿼리 문제입니다~~

 

???: 아니, 골드5잖아요? 왜 제목엔 실버 상위권이라 써놨습니까?!?

 

저는 제목에 solved.ac 티어를 쓰기보다는, 제가 생각하는 이 문제의 난이도를 씁니다.

대체로, solved.ac 티어는 우리에게 거의 정확한 난이도를 알려주는 지표이지만,

일부 문제는 다른 문제보다 쉬운데도 높은 티어로 투표돼 있기도 하고,

심지어 일부 문제는 다른 문제와 완전히 동일한데도 티어차가 어마어마한 경우도 있습니다..!!

이러한 이유입니다... 하하하

 

심지어, 이 문제는 밑에 힌트가 너무 꿀인데다, 트리를 만들고 간단한 dp table만 만들어주면 되기 때문에

개인적으론 Silver II ~ Silver I으로 가도 된다고 생각합니다.

---

의식의 흐름.

수열과 쿼리가 어려웠던 것처럼, 트리와 쿼리는 얼마나 어려울까 하고 쫄았었던 문제.

일단 트리를 만들고 dfs를 열심히 돌려보자는 생각에 양방향으로 트리를 만들어주면 되겠다.

N<=100,000 이고, 쿼리의 개수도 100,000개까지 있으니 dp를 하지 않으면 dfs의 시간복잡도가 O(N+M)이니까  O(Q(N+M))=O(QN)=O(10^10)이니까 무조건 시간초과가 나겠네? 문제에서 요구하는 서브트리 노드의 개수를 dp table에 저장해놓아야겠다. 그 이후론 dfs를 돌리면서 생각해보지 뭐. dfs 돌릴 때마다 +1 해주면 되지 않을까?

---

해결 방법.

역시나 의식의 흐름대로였다. 그냥 그 그대로다...

vector<int> v[MAX];	// 트리
bool visit[MAX];	// dfs니까 방문여부 변수는 필수!
int d[MAX];	// dp table

위와 같이 변수 세팅을 해주고~

각 트리의 노드 정점개수에 자신 포함이므로 fill함수로 1로 초기화해주자.

int dfs(int x) {
	if (visit[x])	// 이미 방문한 경우면 return~
		return d[x];
	visit[x] = true;	// visit 처리를 반드시 먼저 하자!
	for (auto i : v[x]) {
		if (!visit[i]) {
			d[x] = d[x] + dfs(i);
		}
	}
	return d[x];
}

이렇게 평범하게 dfs를 돌면 된다.

아직 이게 어렵다 싶으면 dfs를 연습해야된다.

---

주의사항.

treeDP를 연습하기 좋은 문제.

문제는 이 문제를 연습한 이후로, treeDP를 연습하려고 다른 문제를 찾아보면 난이도가 급상승한다...

---

소스 코드.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100001;
vector<int> v[MAX];
bool visit[MAX];
int d[MAX];
int N, R, Q;
int dfs(int x) {
	if (visit[x])
		return d[x];
	visit[x] = true;
	for (auto i : v[x]) {
		if (!visit[i]) {
			d[x] = d[x] + dfs(i);
		}
	}
	return d[x];
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> R >> Q;
	fill(d, d + MAX, 1);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(R);
	for (int i = 0; i < Q; i++) {
		int q;
		cin >> q;
		cout << d[q] << "\n";
	}
}

조언 및 피드백 언제나 환영입니다!