[백준 15681번] 트리와 쿼리 (C++)

문제링크 : https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, R, Q;
int U,V,u;
int dp[100001];
vector<int>v[100001];
bool visited[100001];

int func(int n)
{
    visited[n]=1; //방문처리
    dp[n]=1; //최소 정점 갯수 1
    for(int i=0; i<v[n].size(); i++)
    {
        if(visited[v[n][i]]) continue; //다음 탐색 대상을 이미 방문했다면 패스
        dp[n]+=func(v[n][i]); //현 위치 기준 연결된 정점들 더해주기
    }
    return dp[n];
}

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

    cin >> N >> R >> Q;
    for(int i=0; i<N-1; i++)
    {
        cin >> U >> V;
        v[U].push_back(V); //양방향
        v[V].push_back(U);
    }
    func(R); //루트를 기준으로 탐색 시작
    for(int i=0; i<Q; i++)
    {
        cin >> u;
        cout << dp[u] << "\n";
    }
}

트리를 사용한 dp 문제이다.

먼저 입력과 동시에 간선을 연결해주고 시작한다.

 

그리고 입력받은 루트 (R)을 기준으로 탐색을 시작한다.

먼저 입력받은 루트(R, 함수 내 n)에 대해서 먼저 dp[n]=1로 초기화를 하고 시작한다.

이는 모든 어떤 정점이든 간에 그에 속한 최소 정점의 갯수가 최소 1개 (자신) 이기 때문이다.

이를 바탕으로 정점들의 갯수를 더해나가게 된다.

 

현재 입력받은 시작점을 기준으로 연결된 다음 값들을 탐색하는데, 이미 방문했다면 패스하도록 한다.

탐색 대상이라면 현재 dp[n]에 연결된 정점들을 재귀를 통해서 더해주게 된다.

 

모든 탐색을 끝내게 되면 dp[u]에 각각 하위 정점들이 몇 개인지 담기게 되므로, 바로 입력받은 u에 대해 dp[u]를 출력해주면 된다.

 

<루트 5>
dp[5] = 1;
dp[5] += 5에 열견된 값 (4, 6)
-----------------------------------------
dp[4] = 1;
dp[4] += 4에 연결된 값 (3)

dp[3] = 1;
dp[3] += 3에 연결된 값 (1, 2)

dp[1] = 1;
연결된 값 x / return dp[1];
dp[2] = 1;
연결된 값 x / return dp[2];

return dp[3] (dp[3] += dp[1] + dp[2] (3))

return dp[4] (dp[4] += dp[3] (4))

-----------------------------------------
dp[6] = 1;
dp[6] += 6에 연결된 값 (7, 8, 9)

dp[7] = 1;
연결된 값 x / return dp[7];
dp[8] = 1;
연결된 값 x / return dp[8];
dp[9] = 1;
연결된 값 x / return dp[9];

return dp[6] (dp[6] += dp[7] + dp[8] + dp[9] (4))

return dp[5] (dp[5] += dp[4] + dp[6] (9))