<Baekjoon> #3584_LCA, DFS 가장 가까운 공통 조상 java

Google 아니고 Joogle·2022년 7월 17일
0

Baekjoon

목록 보기
42/47
post-thumbnail

BOJ #3584

참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..)

🔖Solution

문제 제목에서도 주어진대로 가장 가까운 공통 조상(LCA)을 찾는 문제이다

🔖LCA Algorithm

Lowest Common Ancestor

  1. 모든 노드에 대해 깊이(레벨)를 계산
  2. 최소 공통 조상을 찾을 두 노드를 확인
  3. 두 노드의 깊이가 동일하도록 거슬러 올라감 (깊이가 더 깊은 노드를 깊이가 더 낮은 노드까지 노드를 올려줌)
  4. 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감

개선된 LCA 알고리즘

모든 노드에 대하여 깊이(depth)2^i번째 부모에 대한 정보를 계산 (각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법, 즉 메모리를 더 사용하여 각 노드에 대하여 2^i번째 부모에 대한 정보를 기록)

e.g.

다음과 같이 루트가 1로 고정되어 있고 각 연결된 두 정점에 대한 정보가 input으로 주어질 때, 두 정점의 가장 가까운 공통 조상을 구하는 문제를 풀어보자

  1. 먼저 각 연결된 두 정점에 대한 정보가 input으로 주어질 때 이를 저장한다. 각각 adj배열에 저장된 값은 위에 있는 오른쪽 표와 같다.

    void init() {
        int from, to;
        cin >> N;
    
        for (int i = 0; i < N - 1; i++) {
            cin >> from >> to;
            adj[from].push_back(to);
            adj[to].push_back(from);
        }
    }
  2. 문제에서 루트가 1이라고 지정되어 있으므로 먼저 루트인 1번부터 부모와 레벨을 update힌다. (루트의 부모는 0번 노드라고 지정하고 루트 노드의 레벨은 1이다)
    그 후 루트에서 연결된 다른 노드들을 순서대로 부모와 레벨을 update한다. 이 과정을 모든 노드에 반복한다.

    set_tree(1, 0);
    
    void set_tree(int node, int pnode) {
        // DFS로 트리 구성
    
        parent[node] = pnode;
        level[node] = level[pnode] + 1;
    
        for (int i = 0; i < adj[node].size(); i++) {
            int child = adj[node][i];
            if (child == pnode) continue;
    
            set_tree(child, node);
        }
    }
  3. 모든 노드들의 부모와 레벨을 저장한 후 가장 가까운 공통 조상을 구하고자 하는 두 정점을 입력받고 찾아낸다. 이때 두 정점의 레벨을 맞춰주고 (레벨이 같아질 때까지 루트에서 더 멀리 있는 노드를 위로 끌어올린다), 두 정점의 레벨이 같아졌을 때 두 정점의 부모가 같아질 때까지 같이 올라간다.

int lca(int a, int b) {
	
	//a를 더 level이 높은 정점으로 맞춤
	if (level[a] < level[b]) {
		int tmp = a;
		a = b;
		b = tmp;
	}

	while (level[a] != level[b]) 
		a = parent[a];

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}
	return a;
}

🔖BOJ #3584

이 문제에서 더 추가됐던 점은 루트를 직접 구해야하는 것이다.
그래서 boolean[] rootCheck 변수를 두어 루트의 인덱스를 확인한다

package boj3584;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Solution2 {

	static List<Integer>[] adj;
	static int[] parent, level;
	static boolean[] rootCheck;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader (new InputStreamReader(System.in));
		StringTokenizer st=null;
		
		int T=Integer.parseInt(br.readLine());
		
		for (int tc=1; tc<=T; tc++) {
			int N=Integer.parseInt(br.readLine());
			
			parent=new int[N+1];
			level=new int[N+1];
			adj=new ArrayList[N+1];
			
			for (int j=1; j<N+1; j++)
				adj[j]=new ArrayList<>();
			
			boolean[] rootCheck=new boolean[N+1];
			Arrays.fill(rootCheck, true);
			
			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());
				
				adj[A].add(B);
				adj[B].add(A);
				rootCheck[B]=false;
			}
			
			int rootIdx=0;
			for (int k=1; k<N+1; k++) { 
				if (rootCheck[k]) {
					rootIdx=k;
					break;
				}
			}
			
			setTree(rootIdx, 0);
			
			st=new StringTokenizer(br.readLine()," ");
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			
			System.out.println(LCA(a,b));
		}
	}
	
	static void setTree(int node, int pnode) {
		parent[node]=pnode;
		level[node]=level[pnode]+1;
		
		for (int child : adj[node]) {
			if (child != pnode) {
				setTree(child, node);
			}
		}
	}
	
	
	static int LCA (int a, int b) {
		if (level[a]<level[b]) {
			int tmp=a;
			a=b;
			b=tmp;
		}
		
		while (level[a]!=level[b]) 
			a=parent[a];
		
		while (a!=b) {
			a=parent[a];
			b=parent[b];
		}
		
		return a;
	}
}

Reference
https://velog.io/@shiningcastle/%EC%B5%9C%EC%86%8C-%EA%B3%B5%ED%86%B5-%EC%A1%B0%EC%83%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://www.crocus.co.kr/660

profile
Backend 개발자 지망생

0개의 댓글