[백준] 11437 LCA - 트리(Tree) + DP + LCA(Lowest Common Ancestor) JAVA

https://www.acmicpc.net/problem/11437

11437번: LCA

코드설명

트리, 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;
			}
		}
	}
	
}