[BOJ] 백준 15681 트리와 쿼리 (Swift)

문제

https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

풀이

트리에서 DFS + DP를 사용하여 풀 수 있는 문제입니다.
r을 루트노드인 트리에서 탐색을 하면서, 서브트리에 속한 정점의 수를 계산할 수 있습니다.
이를 계산하면서, 모든 정점에 대해서 각 정점을 루트로 하는 서브트리에 속한 정점의 수를 DFS + DP를 사용해 계산할 수 있습니다.

소스코드

	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let n = input[0], r = input[1], q = input[2]
	var edges = [[Int]](repeating: [], count: n + 1)
	for _ in 0..<n - 1 {
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let u = input[0], v = input[1]
	edges[u].append(v)
	edges[v].append(u)
	}
	var size = [Int](repeating: 0, count: n + 1)
	func dfs(node: Int) {
	size[node] = 1
	for nextNode in edges[node] {
	if size[nextNode] == 0 {
	dfs(node: nextNode)
	size[node] += size[nextNode]
	}
	}
	}
	dfs(node: r)
	var answer = ""
	for _ in 0..<q {
	let node = Int(readLine()!)!
	answer += "\(size[node])\n"
	}
	print(answer)

view raw 트리와 쿼리.swift hosted with ❤ by GitHub

후기

트리에서 다이나믹 프로그래밍 기법을 사용하는 문제를 처음 풀어봤는데,
문제 설명이 자세히 되어있어서 이해하기 쉬웠던 문제였습니다.