N(2 ≤ N ≤ 100,000)개의 노드로 이뤄진 트리가 주어진다. 트리의 각 노드는 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍M(1 ≤ M ≤ 100,000)개가 주어졌을 때 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하시오
(시간 제한 1.5초)
입력
1번째 줄에 노드의 개수 N, 그 다음 N - 1개 줄에는 트리상에 연결된 두 노드가 주어진다. 그 다음 줄에 가장 가까운 공통 조상을 알고 싶은 쌍의 개수 M이 주어지고, 그 다음 M개의 줄에는 노드 쌍이 주어진다.
출력
M개의 줄에 차례대로 입력받은 두 노드의 가장 가까운 공통 조상을 출력한다.
예제 입력
15 // 노드 개수
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6 // 질의 개수
6 11
10 9
2 6
7 6
8 13
8 15
예제 출력
2
4
2
1
3
1
1단계 - 문제 분석하기
노드의 개수와 질의의 개수가 매우 큰 '최소 공통 조상 구하기' 문제다. 그렇기 때문에 일반적인 '최소 공통 조상 구하기' 방식이 아닌 '빠르게 최소 공통 조상 구하기' 방식으로 이 문제를 풀어야 한다.
2단계 - 손으로 풀어 보기
1 인접 리스트로 트리 데이터를 구현한다.
2 탐색 알고리즘(DFS, BFS)을 이용해 각 노드의 깊이를 구한다.
3 점화식을 이용해 부모 노드 배열을 구한다
- P[K][N] = P[K - 1][P[K - 1][N]]
4 깊이가 큰 노드는 부모 노드 배열을 이용해 만큼 이동시켜 깊이를 맞춘다.
8 15의 질의에선 깊이가 2() 만큼 차이가 나므로 15번 노드를 15의 1 번째 부모 노드인 5로 변경해 깊이를 맞춘다.
5 부모 노드로 올라가면서 최소 공통 조상을 찾는다. parent 배열을 이용해 만큼 넘어가면서 찾는다. k는 depth의 최댓값에서 1씩 감소시킨다.
3단계 - sudo코드 작성하기
tree(인접 리스트 자료 구조)
N(수의 개수), M(질의 수)
depth(노드 깊이 배열) parent(노드 부모 배열)
visited(방문 여부 저장 배열)
for(N의 개수만큼 반복)
{
tree 인접 리스트의 각 ArrayList 초기화
}
for(N-1 만큼 반복)
{
tree 인접 리스트에 그래프 데이터 저장
}
kmax(최대 가능 높이) 구하기
parent = new int[kmax + 1][N + 1]
BFS(1)로 각 노드의 깊이 구하기
for(kmax만큼 반복하기)
{
for(노드 개수만큼 반복하기)
{
parent[k][n] = parent[k - 1][parent[k - 1][n]]
}
}
for(M의 개수만큼 반복)
{
a(1번 노드) b(2번 노드)
executeLCA(a, b)
}
executeLCA(int 1번 노드, int 2번 노드)
{
1번 노드의 depth가 더 작으면 2번 노드와 swap
두 노드의 depth를 동일하게 맞추기
두 노드의 같은 조상이 나올 때까지 각 노드를 부모 노드로 변경하는 작업 반복
최소 공통 조상 노드 리턴
}
BFS(int 출발노드)
{
큐 자료구조에 출발 노드 add
visited 배열에 현재 노드 방문 기록
while(큐가 빌 때까지)
{
큐에서 노드 데이터 poll
for(현재 노드의 연결 노드 개수만큼 반복)
{
if(방문하지 않은 노드라면)
{
큐에 데이터 add
visited 배열에 방문 기록
parent 배열에 자신의 부모 노드 저장
depth 배열에 현재 높이 저장
}
}
if(이번 높이에 해당하는 모든 노드를 방문했다면)
{
현재 배열의 depth 1 증가
}
}
}4단계 - 코드 구현하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Q75 {
static ArrayList<Integer>[] tree;
static int[] depth;
static int[][] parent;
static boolean[] visited;
static int kmax;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
tree = new ArrayList[N + 1];
depth = new int[N + 1];
visited = new boolean[N + 1];
for(int i = 1; i < N+1; i++){
tree[i] = new ArrayList<>();
}
for(int i = 0; i < N-1; i++){
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
tree[S].add(E);
tree[E].add(S);
}
int tmp = 1;
kmax = 0;
while(tmp <= N){
tmp *= 2;
kmax++;
}
parent = new int[kmax + 1][N + 1];
BFS(1);
for(int k = 1; k <= kmax; k++){
for(int n = 1; n < N+1; n++){
parent[k][n] = parent[k-1][parent[k-1][n]];
}
}
int M = Integer.parseInt(br.readLine());
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int LCA = executeLCA(a, b);
System.out.println(LCA);
}
br.close();
}
static int executeLCA(int a, int b){
if(depth[a] > depth[b]){
int tmp = a;
a = b;
b = tmp;
}
for(int k = kmax; k >= 0; k--){
if(Math.pow(2, k) <= depth[b] - depth[a]){
if(depth[a] <= depth[parent[k][b]]){
b = parent[k][b];
}
}
}
for(int k = kmax; k >= 0; k--){
if(parent[k][a] != parent[k][b]){
a = parent[k][a];
b = parent[k][b];
}
}
int LCA = a;
if(a != b){
LCA = parent[0][LCA];
}
return LCA;
}
private static void BFS(int node){
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(node);
visited[node] = true;
int level = 1;
int now_size = 1;
int count = 0;
while (!queue.isEmpty()){
int now_node = queue.poll();
for(int next : tree[now_node]){
if(!visited[next]){
visited[next] = true;
queue.add(next);
parent[0][next] = now_node;
depth[next] = level;
}
}
count++;
if(count == now_size){
count = 0;
now_size = queue.size();
level++;
}
}
}
}
- Do it! 알고리즘 코딩테스트 자바 편
