백준 19542 - 전단지 돌리기

백준 19542 - 전단지 돌리기

[문제 바로가기]

1. 유형

깊이 우선 탐색, 트리

2. 문제 접근

2-1. 해설

우선 저는 현재 위치와 leaf노드까지의 깊이를 탐색했습니다.

그림-1

그림 1처럼 만드는 것은 재귀를 사용해서 return값에 +1을 해주면 됩니다.

하지만 저기서도 문제가 있습니다.

2,3,4 노드 같은 여러 가지로 뻗어나가는 부분이 까다롭습니다.

그림2

그래서 그림2 처럼 여러 가지로 뻗어나가는 경우는 리턴 값 중 최댓값을 노드의 깊이로 선택하면 됩니다.

그림 1처럼 노드의 최대 깊이를 탐색했으면 D보다 큰 녀석들의 갯수를 카운트해주고, 왕복이니깐 *2를 해주면 정답이 나옵니다.

2-2. 설계

3. 코드

import java.io.*; import java.util.*; public class Main { static boolean visit[]; static int N,M,D,dp[]; static List list[]; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); N = stoi(st.nextToken()); M= stoi(st.nextToken()); D= stoi(st.nextToken()); list= new ArrayList[N+1]; visit= new boolean[N+1]; dp = new int[N+1]; for(int i=0; i<=N; i++) { list[i]=new ArrayList<>(); } for(int i=0; i=D) { ans++; } } System.out.println(ans*2); } static int dfs(int node) { int val=0; for(int next: list[node]) { if(!visit[next]) { visit[next]=true; val=Math.max(val, dfs(next)); } } dp[node] = val; return dp[node]+1; } static int stoi(String s) { return Integer.valueOf(s); } }

from http://moons-memo.tistory.com/242 by ccl(A) rewrite - 2021-09-09 21:26:19