반응형
문제
https://www.acmicpc.net/problem/15681
15681번: 트리와 쿼리
트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
www.acmicpc.net
풀이
트리에서 DFS + DP를 사용하여 풀 수 있는 문제입니다.
r을 루트노드인 트리에서 탐색을 하면서, 서브트리에 속한 정점의 수를 계산할 수 있습니다.
이를 계산하면서, 모든 정점에 대해서 각 정점을 루트로 하는 서브트리에 속한 정점의 수를 DFS + DP를 사용해 계산할 수 있습니다.
소스코드
후기
트리에서 다이나믹 프로그래밍 기법을 사용하는 문제를 처음 풀어봤는데,
문제 설명이 자세히 되어있어서 이해하기 쉬웠던 문제였습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 2533 사회망 서비스(SNS) (Swift) (0) | 2023.05.23 |
|---|---|
| [BOJ] 백준 1949 우수 마을 (Swift) (0) | 2023.05.23 |
| [BOJ] 백준 17472 다리 만들기 2 (Swift) (0) | 2023.05.18 |
| [BOJ] 백준 6497 전력난 (Swift) (0) | 2023.05.18 |
| [BOJ] 백준 1774 우주신과의 교감 (Swift) (0) | 2023.05.18 |
