백준 15681 c++ "트리와 쿼리" -PlusUltraCode-

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

[필자 사고]

트리 문제다. 트리의 sub트리의 갯수를 구하는 문제는 dFS를 이용하여 구할 수 있다. 

dfs를 들어가면 방문처리 및 subSize의 크기를 1로 설정한 뒤 

현재 위치부터 방문 할 수 있는 for문을 돌아주고 

subSize[u] +=dfs(v)

 

return subSize[u] 형태로 코드를 짜면 쉽게 해결 가능하다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

dfs 함수

• 매개변수 u는 현재 탐색할 정점입니다.
• 이 함수는 재귀적으로 호출되면서 각 정점을 루트로 하는 서브트리의 크기를 계산합니다.

동작 과정

1. visited[u] = true
   • 현재 정점을 방문 처리합니다.
2. subSize[u] = 1
   • 현재 정점 자신을 포함하여 서브트리 크기를 1로 시작합니다.
3. for (int v : adj[u])
   • u에 연결된 모든 인접 정점 v에 대해 반복합니다.
   • 이때, if (visited[u] == false)라는 조건이 들어 있는데, 사실 올바른 조건은 if (visited[v] == false)여야 합니다.
   • 그래야 아직 방문하지 않은 자식 노드로 재귀 호출할 수 있습니다.
4. subSize[u] += dfs(v)
   • 방문하지 않은 자식 정점으로 내려가 DFS를 호출하고, 그 결과(자식 서브트리 크기)를 현재 정점의 크기에 더합니다.
5. 모든 인접 정점을 확인한 뒤, subSize[u]를 반환합니다.

---

main 함수

1. 입력 처리
   • N: 정점의 수
   • R: 루트의 번호
   • Q: 쿼리 개수
   • 이어서 N-1개의 간선을 입력받아 무방향 그래프 형태로 adj에 저장합니다.
2. DFS 실행
   • dfs(R)을 호출하여, 루트 R을 시작으로 전체 트리를 탐색하며 각 노드의 subSize 값을 채웁니다.
   • 이 과정에서 모든 정점의 서브트리 크기가 계산되어 저장됩니다.
3. 쿼리 처리
   • 쿼리마다 정점 번호 u가 주어집니다.
   • cout << subSize[u]로 해당 정점을 루트로 하는 서브트리의 크기를 바로 출력합니다.
   • subSize가 이미 DFS에서 채워져 있기 때문에 쿼리마다 O(1)에 답할 수 있습니다.

---

전체 흐름 요약

• 그래프 입력: 무방향 트리 구조를 인접 리스트로 저장
• DFS 탐색: 루트에서 시작해 각 노드의 서브트리 크기를 계산
• 쿼리 응답: 미리 계산된 subSize 배열을 이용해 즉시 출력

[소스 코드]

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[100001];
int subSize[100001];
bool visited[100001];

int dfs(int u) {
	visited[u] = true;
	subSize[u] = 1;

	for (int v : adj[u]) {
		if (visited[u] == false) {
			subSize[u] += dfs(v);
		}
	}
	return subSize[u];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N, R, Q;
	cin >> N >> R >> Q;
	
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}


	dfs(R); // 루트부터 서브트리 크기 계산

	while (Q--) {
		int u;
		cin >> u;
		cout << subSize[u] << "\n";
	}
}