트리2 [백준] 15681 트리와 쿼리 (Java) [15681 트리와 쿼리] 난이도: 골드5 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 트리를 생성해준 뒤 쿼리 개수만큼 정점의 수를 구했는데, 시간 초과가 났다. 그래서 문제 아래 있는 힌트대로 정점의 개수를 구하는 함수를 구현해주었다. [JAVA 코드] import java.io.*; import java.util.*; public class Main { static BufferedReader br = n.. 2022. 5. 20. [백준] 3584 가장 가까운 공통 조상 (Java) [3584 가장 가까운 공통 조상] 난이도: 골드4 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 입력 출력 [아이디어] 노드마다 부모는 단 하나만 존재한다. 그래서 노드의 부모를 저장해주는 배열을 따로 만들어주었다. parent[i] = j => i 의 부모가 j 이다. 그 다음 두 노드 중 하나의 노드부터 시작하여 루트까지 방문을 체크해준다. 그 후 나머지 노드에 대해 루트까지 올라가면서 방문한 노드를 만나면 그게 가장 가까운 공통 노드가 된다! .. 2022. 5. 12. 이전 1 다음
