트리3

• 

  백준 - 트리의 기둥과 가지 문제 설명 트리의 기둥의 길이와 기가 노드로부터 뻗어있는 가장 멀리 뻗어 있는 가지의 길이를 구하는 문제이다. 주의사항 트리의 기둥부터 기가노드 까지의 판별은 보통 나가는 간선의 개수가 3개 이상일 때 기가노드로 판단할 것이다. 하지만 예외 상황이 있다. 루트에서 기가노드의 길이가 0일 때이다. 1번이 루트라고 주어진다면, 1→2(1), 1→3(1) 으로 갈경우 그러면 기둥의 길이는 2가 되고 가지의 길이는 0이될 것이다. 정답 기둥의 길이가 0이고 가지의 길이가 0이 되어야 한다. 생각한 아이디어 DFS 풀이 private static int root; static class Node { private int v, edge; public Node(int v, int edge) { this.v = v; .. Algorithm/백준 2023. 3. 21.

• 

  백준 - 사촌 문제 설명 사촌 노드의 개수를 구하는 문제이다. 사촌 노드의 사전적 정의 같은 레벨의 노드 여야 한다. 단 같은 부모를 가지면 안된다(:= 형제 노드이면 안된다) 생각한 아이디어 Map을 이용하여 같은 레벨의 노드를 담아냈다. 하지만 형제노드인지를 구별 할 수 없었다. FAIL 각 노드의 부모를 나타내는 배열을 선언하고 같 정점의 값이 부모를 향하도록 구성하였다. SUCCESS 풀이 public static void main(String[] args) throws IOException { StringBuilder answers = new StringBuilder(); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));.. Algorithm/백준 2023. 3. 20.

• 

  백준 - 나무 위의 빗물 문제 설명 최초 루트 노드에 물이 존재하고 루트를 기점으로 물이 자식에게 분배된다. 그러면 기대하는 값(pi)이 0보다 큰 경우의 평균을 구하는 것이다. i번 정점에 쌓인 물의 양의 기댓값을 Pi라 하자. 이때, Pi가 0보다 큰 정점들에 대해서 Pi들의 평균은 어느 정도가 될까? 생각한 아이디어 루트에서 부터 탐색하면서 자식에게 물의 값을 양도하도록 직접 구현했다. 하지만 FAIL 왜 Fail이 나는지 몰랐었다. Pi가 0보다 큰 정점들에 대해서 Pi들의 평균 → pi가 0보다 큰 값인지 실제로 체크를 했다. 나의 구현에서는 root의 물의 양이 1일 때 하나의 정점에서만 pi>0 을 만족해서 물의 양도 :1, 총 점정 : 1로 1/1 = 1.0000000000 으로 출력했다. 그래서 FAIL이 난 것.. Algorithm/백준 2023. 3. 16.