#15681 : 트리와 쿼리

풀이방법

사용된 것:

동적 프로그래밍

깊이우선탐색(DFS)

 

2022.02.23

오답노트 #15681 : 트리와 쿼리

 

동적 프로그래밍을 사용한다.

 

n번 노드의 자식이 m1, m2라 할 때,

n의 서브노드의 개수는

m1의 서브노드 개수 + m2의 서브노드 개수 + 1 이다.

 

따라서 이 문제는 동적 프로그래밍으로 풀기에 알맞다.

 

간선정보를 일단 이중 ArrayList에 저장해둔다.

이 정보를 활용하여,

루트에서 출발하여 모든 노드를 DFS 순서에 따라 방문한다.

방문하면서, 각 노드의 서브노드 개수를 DP식으로 차곡차곡 더해가며 메모이제이션한다.

이렇게 완성한 노드 개수 배열에서 필요한 값을 꺼내와 출력하면 문제 해결이다.

 

 

이번 문제를 풀면서 배운 것이 있다.
트리의 노드를 루트부터 순서대로 방문하는 것을, 간선 정보 배열만 가지고도 충분히 할 수 있다는 사실이다.

나는 지금까지 계속
각 노드의 부모가 누구고 자식이 누군지를 다~~~~ 기록해놓고 문제풀이를 시작했다.

이 문제를 풀 때도 처음에는
parent 변수와 child 배열을 필드로 가지는 객체들의 배열을 만들어,
트리를 완벽히 구현한 다음에 연산을 수행하려 했다.
근데 그럴 필요가 전혀 없었다.

인간인 나는 멍청해서 동그라미와 직선으로 트리를 그려놓아야 트리 문제를 풀 수 있지만 컴퓨터는 그렇지 않다...
그런 준비작업은
'주어지는 노드의 부모 노드 번호를 즉시 출력하시오'라는 주문이 들어올 때처럼,
각 노드의 부모가 누구고 자식이 누군지 일일이 미리 적어두는 게 효율적인 상황일 때만! 하면 된다.

 

코드

Java(2022.02.23)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int n, r, q;
	static ArrayList<ArrayList<Integer>> tree;	//간선정보를 저장함
	static int[] dp;	//각 노드당 서브노드의 개수를 저장함
	static StringTokenizer st;
	static StringBuilder sb;
	
	static int makeTree(int cur, int parent) {		
		for(Integer a: tree.get(cur)) {
			//자신과 이어진 노드 중 부모가 아닌 것(자식들)의 dp값을 모두 스스로에게 더함
			if(a != parent) dp[cur] += makeTree(a, cur);
		}
		//재귀를 위해 자신의 dp값을 리턴
		return dp[cur];
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//n, r, q 읽어오기
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		q = Integer.parseInt(st.nextToken());
		
		dp = new int[n+1];
		
		//트리 만들기
		tree = new ArrayList<>();
		for(int i = 0; i<n+1; i++) {
			tree.add(new ArrayList<Integer>());
		}
			//간선 읽어오기
		for(int i = 0; i<n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		Arrays.fill(dp,1);
		makeTree(r, -1);
		
		//쿼리에 답하기
		sb = new StringBuilder();
		for(int i = 0; i<q; i++) {
			int u = Integer.parseInt(br.readLine());
			sb.append(dp[u] + System.getProperty("line.separator"));
		}
		System.out.print(sb);

	}

}