[BOJ] 백준 19542번 전단지 돌리기 (Java)

#19542 전단지 돌리기

난이도 : 골드 4

유형 : 트리 / DFS 

19542번: 전단지 돌리기

▸ 문제

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

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

▸ 입력

첫번째 줄에는 노드의 개수 N(1≤N≤100)과 케니소프트의 위치 S(1≤S≤N), 힘 D(0≤D≤N)이 주어진다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드가 연결되어 있음을 의미한다. (1≤x,y≤N, x≠y)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1이다.

▸ 출력

현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.

 

문제 풀이  

처음에 문제 이해가 잘안됐는데 알고보니 거리가 D 이하인 노드까지 움직일 수 있는 것이 아니라 D거리 이하에 있는 노드는 방문하지 않고전단지를 배포할 수 있다는 뜻이었다. 이는 트리 DFS 탐색으로 구할 수 있다. D의 거리는 리프노드부터의 거리를 세어준다. D보다 값이 커지는 일정 노드부터 현민이가 이동해야 하는 노드이다. 

 

D가 1인 트리가 다음과 같이 주어졌을 때 파란색을 칠한 노드만 탐색해주면 된다. 트리의 최단 거리는 교차 간선이 없기 때문에 간선의 수*2를 해주면 된다. 

 

D가 1일 경우

 

설계

1. 입력 데이터를 인접리스트 배열에 저장한다. (x, y가 항상 부모-자식 관계의 순서로 주어지는 것이 아니기 떄문에 양방향으로 입력받아야 한다.)
2. s를 시작점으로 dfs 트리를 탐색한다. dfs(s, -1);
   1. 리프노드를 시작으로 depth를 1씩 증가시킨다. 서브노드가 2개 이상일 경우 더 깊은 depth값을 적용한다. 
   2. depth >= d, cnt++; 노드의 거리가 d가 넘는 경우 탐색해야 하는 노드이므로 카운트해준다. 
      
      1. 시작점은 카운트하지 않아도 된다.
3. 왕복 간선의 갯수 = 시작점을 제외한 방문노드의 갯수*2를 출력해준다. cnt*2

 

풀이 코드 

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

public class Main {

	static int n,s,d,cnt;
	static List<Integer>[] list;
	static int[] depth;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		
		depth = new int[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		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());
			list[a].add(b);
			list[b].add(a);
		}
		
		dfs(s, -1);
		System.out.println(cnt*2);
	}
	
	static int dfs(int idx, int pa) {
		for(int nxt : list[idx]) {
			if(nxt != pa) {
				depth[idx] = Math.max(depth[idx], dfs(nxt, idx)+1);
			}
		}
		
		if(idx!=s && depth[idx] >=  d) {
			cnt++;
		}
		return depth[idx];
	}
}