https://www.acmicpc.net/problem/11437
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
코드설명
트리, DP, LCA 문제입니다.
트리에서 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)를 찾는 문제입니다.
이 문제같은경우, BFS와 DFS로 방식으로 각각 구현해보았습니다.
문제의 핵심 로직입니다.
1.먼저 사용할 데이터입니다. depth[] : 트리에서 각 노드의 깊이를 의미합니다., parent[] : 트리에서 각 노드의 부모를 의미합니다, visited[] : 트리에서 방문여부를 확인합니다.
2. DFS를 사용하여 각 노드의 깊이(depth)와 부모 노드(parent)를 설정합니다.
3. 최소 공통 조상(LCA) (Finding Lowest Common Ancestor)를 통해 주어진 두 노드의 깊이를 비교하여 높이를 맞추고, 그 후에 공통 조상을 찾습니다.
코드
DFS 로 푼 코드 + getLCA 코드의 로직 수정
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 Main {
public static int N, M;
public static int[][] map;
public static StringBuilder sb = new StringBuilder();
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static int[] depth;
public static int[] parent;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
for(int i=0;i<=N;i++) {
graph.add(new ArrayList<Integer>());
}
depth = new int[N+1];
parent = new int[N+1];
visited = new boolean[N+1];
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());
graph.get(a).add(b);
graph.get(b).add(a);
}
visited[1] = true;
dfs(0, 1, 1);
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(getLCA(a,b)).append("\n");
}
System.out.println(sb.toString());
}
public static int getLCA(int a, int b) { //최소공통조상을 구합니다.
int aH = depth[a];
int bH = depth[b];
while(aH > bH) { //서로의 높이를 맞춰줍니다.
a = parent[a];
aH-=1;
}
while(aH < bH) {
b = parent[b];
bH -=1;
}
//같은 조상이 나올때까지 한칸씩 올라가비다.
while(a != b) {
a = parent[a];
b = parent[b];
}
return a;
}
public static void dfs(int level, int curNode, int parentNode) {
parent[curNode] = parentNode;
depth[curNode] = level;
for(int i=0; i<graph.get(curNode).size(); i++) {
int nextNode = graph.get(curNode).get(i);
if(visited[nextNode] == false) {
visited[nextNode] = true;
dfs(level + 1, nextNode, curNode);
}
}
}
}
BFS로 푼 코드
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 Main {
public static int N, M;
public static int[][] map;
public static StringBuilder sb = new StringBuilder();
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static int[] depth;
public static int[] parent;
public static boolean[] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
for(int i=0;i<=N;i++) {
graph.add(new ArrayList<Integer>());
}
depth = new int[N+1];
parent = new int[N+1];
visited = new boolean[N+1];
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());
graph.get(a).add(b);
graph.get(b).add(a);
}
BFS(1);
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(getLCA(a,b)).append("\n");
}
System.out.println(sb.toString());
}
public static int getLCA(int a, int b) { //최소공통조상을 구합니다.
if(depth[a] < depth[b]) { //만약 b의 depth가 a보다 더 깊다면, a와 b를 swap 시켜서 a를 더 깊게 만듭니다. 무조건적으로 a가 더 깊게 만들어서 올라오도록 할것입니다.
int temp = a;
a = b;
b = temp;
}
while(depth[a] != depth[b]) { //만약 a와 b의 depth가 다르다면, a를 부모노드로 1칸씩 옮겨주며 깊이를 맞춥니다.
a = parent[a];
}
//같은 조상이 나올때까지 한칸씩 올라가비다.
while(a != b) {
a = parent[a];
b = parent[b];
}
return a;
}
public static void BFS(int startNode) {
Queue<Integer> q = new LinkedList<>();
q.offer(startNode);
visited[startNode] = true;
depth[startNode] = 1;
parent[startNode] = startNode;
int level = 0; //현재 높이를 저장합니다.
int q_size = q.size();
int cnt = 0;
while(!q.isEmpty()) {
int temp = q.poll();
for(int i=0;i<graph.get(temp).size();i++) {
int child = graph.get(temp).get(i);
if(visited[child] == false) {
visited[child] = true;
parent[child] = temp; //부모노드를 저장합니다.
depth[child] = level; //깊이를 저장합니다.
q.offer(child);
}
}
cnt += 1;
if(cnt == q_size) {
cnt = 0;
q_size = q.size();
level += 1;
}
}
}
}