백준 문제풀이(JAVA)/트리 (3) 썸네일형 리스트형 백준 1761번(JAVA) - 정점들의 거리 import java.util.*; import java.io.*; class Node { int v; int w; Node(int v, int w) { this.v=v; this.w=w; } } public class Main { public static ArrayList[] arr; public static int N; public static int[] Depth; // 깊이 public static int[][] parent;// parent[0][3] 은 3번 노드의 2의0승 부모, //parent[5][3]은 3번 노드의 2의 5승부모, 즉 32번째 부모 public static int[][] length;// length[5][3] 은 3번 노드부터 2의0승 부모까지의 길이 public st.. 백준 3176번(JAVA) 백준 문제중 11438번 LCA2가 있는데, 트리를 타고 올라갈때 한 칸 씩 올라가는게 아니라 2의N승씩 올라가는 빠른 LCA가 있다. 밑에 문제를 풀 줄 안다면 이번 3176번도 손 쉽게 풀 수있다. https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 빠른 LCA탐색 문제는 부모를 2의N승 부모를 저장한다. 예를들어 위 그림과 같은 트리가 있다고 가정해보자. 기존에는 바로 위의 부모만 저장했다. 그래서 .. 백준 14267번(JAVA) 기본적으로 트리를 생성할 줄 안다면 수월하게 풀 수있다. 나 같은경우에는 ArrayList로 트리를 구현했다. 문제에서는 직속부하와 상사라고 표현했지만 직속부하는 자식 노드, 상사는 부모 노드, 사장은 루트노드라고 생각하고 풀면된다. 우선 부모자식 관계를 입력받는다. 그 후 따로 선언해놓은 int[] result배열에 각각의 칭찬수치를 더한다. 예를들어 2번직원이 2만큼 칭찬받았다면 result[2]=result[2]+2, 3번직원이 4만큼 칭찬받았다면 result[3]=result[3]+4, 이런식으로 그 후 사장노드부터 DFS를 실시하는데 실시할때 부모노드의 result값을 자식노드의 result값에 더한다. 그리고 result를 1부터 n까지 출력하면 끝. 핵심은 DFS를 사장부터 시작하고 부모노드.. 이전 1 다음
