[BOJ] 19542.전단지 돌리기(그래프, DFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

리프 노드까지 쭉 내려갔다가

올라오면서 자신에게 자식 노드가 몇 개 있는지 카운트해서 저장해주어야한다.

그렇게 카운트가 구해지면 

힘보다 크거나 같은 자식 노드를 갖는 노드만 방문해주면 된다.

왜냐?!

힘이 3일 때, 자식 노드를 3개 가진 노드를 방문했고 하자.

그러면 해당 노드만 방문하고도 그 노드의 자식 노드까지 모두 전단지를 돌릴 수 있다.

쭈우욱 내려갔다가 올라오면서 카운트를 해줘야하므로 

DFS로 해결하는게 좋을 것 같다.

이렇게 말은 쉽다..

구현이 문제지 하핳..

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class BOJ19542 {       static int N, S, D, dist[];     static ArrayList<Integer> relation[];       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()); // 힘         relation = new ArrayList[N + 1];         dist = new int[N + 1];         for (int i = 0; i <= N; i++)             relation[i] = 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());             relation[a].add(b);             relation[b].add(a);         }           dfs(S, 0);           int res = 0;         for (int i = 1; i <= N; i++) {             if (i != S && dist[i] >= D) {                 res += 1;             }         }           System.out.println(res * 2);     }       // 리프노드부터 몇 개의 자식을 가지고 있는지 cnt     public static int dfs(int node, int pnt) {         // 리프 노드는 자식이 없으므로 0         if (node != S && relation[node].size() == 1) {             return dist[node] = 0;         }         for (int i = 0; i < relation[node].size(); i++) {             int next = relation[node].get(i);             // 내 부모 노드면 pass             if (next == pnt) continue;             // 가장 길게 달린 자식노드 수를 저장.             dist[node] = Math.max(dist[node], dfs(next, node) + 1);         }         return dist[node];     } }   Colored by Color Scripter

cs

line 46~59) 자식 노드를 찾아 떠나는 핵심 코드..

line 48) 루트는 하나의 자식 노드와만 관계가 있으므로 제외하고,

  하나의 노드 즉, 부모 노드하고만 관계를 가지고 있는 노드는 리프 노드이다.

line 49) 리프 노드는 자식 노드가 없으므로 0을 저장해주고 return 해주자.

line 51~57) 자신의 자식 노드들을 모두 방문해볼 것이다.

line 54) 여기서 중요한건 자신의 부모 노드가 누구인지 가지고 다녀야 한다.

  그래야 다시 부모 노드로 다시 올라가는 일이 발생하지 않기 때문에!

line 56) 자신의 자식 노드가 가지고 있는 자식의 수 + 1을 해주면,

  내가 가지고 있는 자식 노드의 수가 된다.

  하지만 자식 노드 A는 3명이 자식이 있는데, 자식 노드 B는 1명의 자식을 가지고 있다고 해보자.

  가장 많이 딸린 자식 노드의 수를 가지고 있어야 힘이 어디까지 닿을 수 있을지 알 수 있기 때문에

  max로 이러한 상황을 처리해주어야 한다.

line 58) 현재 노드의 자식 수를 모두 파악했다면 부모 노드에게 내가 몇 개의 자식 노드를 가지고 있는지

  알려주어야 한다. 그래야 부모 노드도 몇 개의 자식 노드가 있는지 카운트할 수 있으니까..

line 36~42) 자식의 수가 힘보다 크거나 같은 노드만 방문해주면 되는데, 

     처음에 방문할 노드의 수 X 2 - 2 를 해주었을 때, 계속 틀린 답이 나왔었다.

 그런데 만일 노드가 1, 2, 3 이 있고, 힘이 4가 주어졌을 때를 생각해보자

 이동을 하지 않고도 전단지를 뿌릴 수 있기 때문에 결과는 0이 나와야 하지만 

 나는 0 x 2 - 2 를 해주어서 결과가 -2 가 나오기 때문이었다.

 그래서 그냥 편하게 출발지점을 제외하고 방문할 노드 x 2 를 해주었다.

 재귀 함수와 친해질(?)수 있었던 문제였다..