#15681 트리와 쿼리
난이도 : 골드 5
유형 : 트리 순회
▸ 문제
간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.
- 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.
만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.
▸ 입력
트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)
이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.
이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)
입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.
▸ 출력
Q줄에 걸쳐 각 쿼리의 답을 정수 하나로 출력한다.
문제 풀이
트리 순회 문제로 후위 순회와 dp를 활용한 문제로 리프노드부터 거슬러 노드의 수를 카운트해주면 된다. dp라고 하기에는 좀 단순하긴 한데 그냥 모든 노드의 값을 1로 초기화하고 매 탐색마다 부모 노드의 데이터에 자식 노드의 수를 더해주면 된다.
설계
- 인접리스트 List<>[] 자료구조에 트리 간선 데이터를 저장한다.
- 루트노드(r)을 시작으로 트리 후위 순회를 한다.
- numOfChild[pa] += numOfChild[idx]; 부모노드에 자식노드의 개수를 더해준다.
- 쿼리에서 주어지는 노드 번호를 numOfChild 배열 인덱스에 대입해 해당 노드의 서브트리에 속한 정점의 수를 출력한다.
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int[] numOfChild;
static List<Integer>[] list;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
list = new ArrayList[n+1];
for(int i=1; i<n+1; i++) {
list[i] = new ArrayList<>();
}
numOfChild = new int[n+1];
Arrays.fill(numOfChild, 1);
for(int i=0; i<n-1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
list[u].add(v);
list[v].add(u);
}
traversal(r, -1);
for(int i=0; i<q; i++) {
int idx = Integer.parseInt(br.readLine());
System.out.println(numOfChild[idx]);
}
}
static void traversal(int idx, int pa) {
for(int nxt : list[idx]) {
if(pa != nxt) {
traversal(nxt, idx);
}
}
if(pa!=-1) {
numOfChild[pa] += numOfChild[idx];
}
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 16437번 양 구출 작전 (Java) (0) | 2021.10.04 |
---|---|
[BOJ] 백준 11812번 K진 트리 (Java) (0) | 2021.10.03 |
[BOJ] 백준 2109번 순회강연 (Java) (0) | 2021.10.01 |
[BOJ] 백준 12904번 A와 B (Java) (0) | 2021.09.30 |
[BOJ] 백준 1700번 멀티탭 스케줄링 (Java) (0) | 2021.09.29 |