[G5] 백준 15681번 트리와 쿼리 C++ DFS, 깊이 우선 탐색, 트리

리뷰

 

알고리즘 분류에 다이나믹 프로그래밍이 있어 혼란이 왔었는데 DFS로도 충분히 AC가 가능한 문제였다.

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

 

문제 풀이

전역 변수

• n, r, q : 노드의 개수 n, 루트 노드 r, 쿼리의 개수q
• dp : 각 노드가 루트인 서브트리에서의 하위 노드의 개수(자신을 포함한다.)
• v : DFS 내부에서 사용할 방문처리 배열, 최대 노드의 개수보다 크게 설정해 준다.
• path : 인접 리스트를 저장할 정수형 벡터 배열, 최대 노드의 개수보다 크게 설정해 준다.

 

1. n, r, q를 각각 입력 받아주고, dp를 n + 1크기로, 기본값은 자기 자신을 포함하기 위해 1로 세팅해 준다.
2. n - 1개의 간선 정보를 입력 받아 양방향 인접 리스트를 생성해 준다.
3. 루트를 방문처리 해주고 루트로 부터 dfs 탐색을 시작해 준다.
4. 인접 리스트를 탐색하며 방문하지 않은 노드라면 방문처리 해주고 자식 노드를 dfs 돌려준다.
5. 재귀를 빠져나오면서 dp의 자식 인덱스 값을 부모의 dp인덱스에 더해준다.
6. 탐색이 종료된 후 q개의 쿼리를 실행해 준다, dp에 index를 통해 바로 출력해 줄 수 있다.

 

참고 사항

1. 모든 노드의 기본 자식의 개수는 자신을 포함하기에 1인 상태로 시작한다.
2. 리프 노드에 도달하면 해당 노드는 인접리스트에서 탐색할 노드가 없을 것이다. (자신의 부모는 이미 방문처리 되어 있기 때문) 그럼 그대로 리턴을 하게 되면서 부모 노드의 dp값은 1이 증가가 된다.
3. 부모노드 마찬가지로 더 이상 탐색할 자식 노드가 없다면 상위 노드의 dp값에 자신의 dp값을 더해주게 된다.
4. 최종적으로 자기자신의 dp인덱스는 자신을 포함한 자신의 자식 개수가 된다.

 

정답 코드

#include<iostream>
#include<vector>

using namespace std;

int n, r, q;
vector<int> dp;
int v[100001] = { 0, };
vector<int> path[100001];

void dfs(int node) {
	for (int child : path[node]) {
		if (!v[child]) {
			v[child] = 1;
			dfs(child);
			dp[node] += dp[child];
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> r >> q;
	dp.resize(n + 1, 1);
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		path[a].push_back(b);
		path[b].push_back(a);
	}
	v[r] = 1;
	dfs(r);
	while (q--) {
		int a; cin >> a;
		cout << dp[a] << "\n";
	}
}