트리8 [백준 Silver 3] 9372 상근이의 여행 - Java 문제링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 접근 과정 : 문제의 접근 방법은 크게 두가지라고 생각한다. 먼저 지나가는 국가를 체크하면서 비행기를 타고, 모든 국가를 다 지나갔을 때, 비행기의 종류를 리턴하는 방법! 그런데 여기에는 약간의 함정이 있다. 국가를 여러번 지나가도 되고, 하나의 비행기를 여러번 타도 된다.!! 즉, 비행기의 종류(간선)이 최소가 되게 모든 국가를 연결하는 것인데 .. 2022. 1. 3. [백준 Gold 3] 11812 K진 트리 - Java 문제링크 : https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 접근 과정 : 트리에서 부모 인덱스로 자식 인덱스를 계산하고, 자식 인덱스로 부모 인덱스를 계산하는 방식을 사용했다. 흔히 이진트리에서는 자식/2가 부모 인덱스가 되는 것처럼 이를 이용해 계산하려고 했다. 자식 인덱스를 보고 부모의 인덱스를 계산할 수 있는 방식이 필요했다. 나는 여려 계산 끝에, 부모 = (자식+K-2)/.. 2022. 1. 3. [백준 Gold 4] 3584 가장 가까운 공통 조상 - Java 문제링크 : https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 접근 과정 : 부모 - 자식 관계가 주어지고 두 노드가 주어졌을 때, 그 두 노드의 가장 가까운 공통 조상을 찾으면 된다. 저장한 부모-자식 관계를 따라서 노드 A의 조상을 체크한다. DFS로 B의 조상을 탐색하면서 A의 조상체크가 되어있는 조상을 발견하면 리턴한다. 소스 코드 및 결과 : package BOJ; /* 가장 가까운 공.. 2022. 1. 2. [백준 Gold 5] 1068 트리 - Java 문제링크 : https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 접근 과정 : 트리에 속한 노드 중 하나를 삭제했을 때, 남아있는 리프노드의 갯수를 구하는 문제이다. 노드를 삭제하면 그 노드의 자식 노드들도 같이 삭제된다. 우선 자식노드를 저장하는 List 를 생성했다. 그리고 삭제할 노드부터 그 이하 자식노드를 모두 boolen[] removed에 체크했다. 이제 0번 노드부터 N-1번 노드까지 순회하면서, 현재 리프노드인 것만 계산했다. .. 2021. 12. 27. 이전 1 2 다음
