백준 - 15681 트리와 쿼리

 

해결과정 - dfs

한 정점을 루트노드로 하여 트리를 구성한뒤 이렇게 구성된 트리에서 각 정점의 서브트리의 개수를 찾아내는 문제이다

처음에는 문제를 빠르게 읽어 각 질의마다 root가 다르게 구성되어서 항상 같은 답을 반환하는게 아닌가? 라는 의문을 가졌는데 루트가 고정되어있다는 사실을 문제를 다시 읽으면서 알게되었다.

 

트리는 탐색하는 대표적인 방법은 bfs와 dfs가 있다 그중에서 dfs를 사용하면 최종 탐색과정이 leaf노드부터 root로 올라가게 된다 이를 이용하여 트리를 탐색하는 동시에 탐색한 노드의 개수를 현재 탐색하고 있는 노드에 저장하게 된다면 그 값들이 곧 이 문제의 답이 되었다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

void dfs(vector<vector<int>>& tree, vector<int>& tree_size, int cur_node)
{
    tree_size[cur_node] = 1;
    for (int i = 0; i < tree[cur_node].size(); i++) {
        int next_node = tree[cur_node][i];
        // 이미 방문한 노드 재방문 방지
        if(tree_size[next_node] != 0) continue;
        dfs(tree, tree_size, next_node);
        tree_size[cur_node] += tree_size[next_node];
    }
}

int main() {
    FAST;

    int node_count, root_number, query_count;
    cin >> node_count >> root_number >> query_count;

    vector<vector<int>> tree(node_count + 1);
    vector<int> tree_size(node_count + 1, 0);

    for (int i = 0; i < node_count - 1; i++)
    {
		int parent, child;
		cin >> parent >> child;
		tree[parent].push_back(child);
        tree[child].push_back(parent);
	}

    dfs(tree, tree_size, root_number);

    for (int i = 0; i < query_count; i++)
    {
		int query;
		cin >> query;
		cout << tree_size[query] << "\n";
	}

    return 0;
}

 

후기

그래프 문제는 대부분 쉬운거 같다 예전에는 그래프가 어렵다 생각했는데 다른 문제들이 더 어렵다