백준 11437번
https://www.acmicpc.net/problem/11437
문제
생각하기
-
LCA 알고리즘 문제이다.
- (Lawest Common Ancestor) 최소 공통 조상 알고리즘
-
DFS/BFS를 통해서 각 노드의 깊이를 구한다.
-
공통 부모를 찾으려는 노드의 깊이를 똑같이 맞춰준다.
- 깊이가 더 깊은 노드를 차이만큼 반복해서 맞춰준다.
-
두 노드를 동시에 부모 노드로 올라가면서 조상을 찾는다.
동작
adjList 인접리스트를 통해서 노드들의 관계를 저장하고 parents[] 배열에 각 노드들의 부모 정보와 depths[] 에 노드의 깊이를 저장한다.
가장 먼저 DFS나 BFS를 사용해서 각 노드들의 깊이를 알아야한다.
private static void DFS(int current, int parent, int depth, int index) {
if (index == 0) {
parents[current] = parent;
depths[current] = depth;
} else if (index == adjList.get(current).size()) return;
int next = adjList.get(current).get(index);
if (next != parent) {
DFS(next, current, depth + 1, 0);
}
DFS(current, parent, depth, index + 1);
} // End of DFS()
adjList를 재귀로 순회하며 next node와 parent가 다를 경우에는 current가 parent가 되고 next가 current가 되며 새로운 노드를 탐색해 간다.
양방향 그래프 개념이므로, next노드와 parent노드가 같게 나올 수 있다. 이럴 경우는 제외하고 next를 current로 계속 갱신하면서 부모 노드를 찾아간다.
private static int LCA(int a, int b) {
// 깊이를 같게 맞춰주기,
while (depths[a] != depths[b]) {
if (depths[a] > depths[b]) {
// a의 깊이가 더 깊으면,
// a의 부모값으로 갱신해서 깊이를 낮춘다.
a = parents[a];
} else {
b = parents[b];
}
}
// 깊이가 같게 맞춰졌으면, 부모를 서로 갱신해서 a와 b가 같을 때 까지 반복해서 같은 부모를 찾기
while (a != b) {
a = parents[a];
b = parents[b];
}
return a;
} // End of LCA()
그리고 만들어진 parents[]와 depths[] 을 사용해서 가장 가까운 공통 조상을 찾아 나간다.
depths[a]와 depths[b]가 다르면 같을 때 까지 높이를 맞춰주는데
depths[a] > depths[b] 처럼 a의 깊이가 더 깊을 경우, a의 깊이를 b와 맞춰야 하므로 a값을 parents[a]의 값으로 갱신해준다. 이 과정을 반복해서 더 깊은 쪽의 노드를 얕은 쪽의 노드로 맞춰줄 수 있다.
그 다음은 a 와 b의 같은 부모를 찾는데, 이미 높이가 같으므로 계속 반복만 하면, 같은 부모를 찾을 수 있다.
결과
코드
DFS + 일반 LCA
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[] depths, parents;
private static List<List<Integer>> adjList;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() throws IOException {
StringBuilder sb = new StringBuilder();
DFS(1, 0, 0, 0);
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(LCA(a, b)).append('\n');
}
return sb.toString();
} // End of solve()
private static void DFS(int current, int parent, int depth, int index) {
if (index == 0) {
parents[current] = parent;
depths[current] = depth;
} else if (index == adjList.get(current).size()) return;
int next = adjList.get(current).get(index);
if (next != parent) {
DFS(next, current, depth + 1, 0);
}
DFS(current, parent, depth, index + 1);
} // End of DFS()
private static int LCA(int a, int b) {
while (depths[a] != depths[b]) {
if (depths[a] > depths[b]) {
// a의 깊이가 더 깊으면,
// a의 부모값으로 갱신해서 깊이를 낮춘다.
a = parents[a];
} else {
b = parents[b];
}
}
while (a != b) {
a = parents[a];
b = parents[b];
}
return a;
} // End of LCA()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
depths = new int[N + 1];
parents = new int[N + 1];
adjList = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
}
StringTokenizer st;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adjList.get(a).add(b);
adjList.get(b).add(a);
}
M = Integer.parseInt(br.readLine());
} // End of input()
} // End of Main class
DFS + 완전재귀 LCA
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[] depths, parents;
private static List<List<Integer>> adjList;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
input();
bw.write(solve());
bw.close();
} // End of main()
private static String solve() throws IOException {
StringBuilder sb = new StringBuilder();
DFS(1, 0, 0, 0);
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(LCA(a, b)).append('\n');
}
return sb.toString();
} // End of solve()
private static void DFS(int current, int parent, int depth, int index) {
if (index == 0) {
parents[current] = parent;
depths[current] = depth;
} else if (index == adjList.get(current).size()) return;
int next = adjList.get(current).get(index);
if (next != parent) {
DFS(next, current, depth + 1, 0);
}
DFS(current, parent, depth, index + 1);
} // End of DFS()
private static int LCA(int a, int b) {
if (a == b) {
return a;
}
// 먼저 깊이를 맞춘다
if (depths[a] > depths[b]) {
return LCA(parents[a], b);
} else if(depths[a] < depths[b]) {
return LCA(a, parents[b]);
}
// 깊이가 같다면 공통 조상을 찾는다
return LCA(parents[a], parents[b]);
} // End of LCA()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
depths = new int[N + 1];
parents = new int[N + 1];
adjList = new ArrayList<>();
for (int i = 0; i <= N; i++) {
adjList.add(new ArrayList<>());
}
StringTokenizer st;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adjList.get(a).add(b);
adjList.get(b).add(a);
}
M = Integer.parseInt(br.readLine());
} // End of input()
} // End of Main class
