백준 19542: 전단지 돌리기

문제 요약

현민이는 트리 모양의 길 위에서 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가 $D$ 이하인 모든 노드에 전단지를 돌릴 수 있다.

현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

문제 분류

• 그래프 이론
• 그래프 탐색
• 트리
• DFS

문제 풀이

트리의 깊이를 이용하는 문제이다. 정점을 탐색하며, 해당 정점으로부터 리프 노드까지의 깊이가 D 이하라면 더이상 방문할 필요가 없다.
이렇게 방문한 정점의 개수에 2를 곱하여 왕복 거리를 구하면 된다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, s, d;
	static List<Integer> e[];
	static boolean visited[];
	static int dep[];
	static int res;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int u, v;
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken()) - 1;
		d = Integer.parseInt(st.nextToken());
		visited = new boolean[n];
		dep = new int[n];
		e = new List[n];
		for(int i = 0; i < n; i++)
			e[i] = new ArrayList<>();
		for(int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			e[u].add(v);
			e[v].add(u);
		}
		visited[s] = true;
		dfs(s);
		sol(s);
		res *= 2;
		System.out.println(res);
	}
	static int dfs(int v) {
		dep[v] = 1;
		for(int it : e[v]) {
			if(!visited[it]) {
				visited[it] = true;
				dep[v] = Math.max(dep[v], dfs(it) + 1);
				visited[it] = false;
			}
		}
		return dep[v];
	}
	static void sol(int v) {
		for(int it : e[v]) {
			if(!visited[it]) {
				if(dep[it] > d) {
					visited[it] = true;
					res++;
					sol(it);
					visited[it] = false;
				}
			}
		}
	}
}