11437 LCA

 

1. 풀이

 

 

 

다른 사람 블로그를 참고했다.

 

일단 그림으로 설명하겠다.

 

 

<그림1>

문제 예제에 6번 노드와 11번 노드의 부모를 찾으라고 되어있다.

이때, 6번 노드와 11번 노드의 level 이 다르다.

트리에서 level 이란, 루트 노드로부터 깊이를 의미하는데, 루트 노드의 level = 1이다.

이때 level 이 더 큰 11번 노드와 관련해서 변화를 준다.

=> 11번 노드의 부모 노드를 타고 이동하면서 노드 6과 level 이 같아지는 노드 번호를 찾는다.

 

 

 

<그림2>

5번 노드와 6번 노드의 level 이 같다.

이때부터는 5번, 6번 노드의 각 부모 노드를 타고 올라가면서 그 값이 같아지는 경우를 찾으면 된다.

5번 노드의 부모 노드와, 6번 노드의 부모 노드가 2로 같다.

정답은 2가 된다.

 

<그림3>

 

위에서는 쉽게 풀렸지만, 다른 경우를 생각해보자.

9번, 11번 노드는 level 이 같다.

하지만 9번 노드의 부모는 4, 11번 노드의 부모는 5이다.

서로 같지 않으므로 부모 노드를 한 번 더 따져봐야 한다.

4번, 5번 노드의 부모노드는 2이므로 같아졌다.

이 경우도 정답은 2가 된다.

 

이런식으로 해결하면 된다.

 

 

 

2. 최종 코드

 

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

public class Main {
	
	static int parents[];
	static int depth[];
	static boolean visit[];
	static ArrayList<ArrayList<Integer>> tree;

	public static void main(String[] args) throws IOException {
				
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		tree  = new ArrayList<>();
		
		for(int i=0; i<=N; i++) {
			tree.add(new ArrayList<>());
		}
		
		parents = new int[N+1];
		depth = new int[N+1];
		visit = new boolean[N+1];
		
		for(int i=0; i<N-1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " " );
			
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			
			tree.get(n1).add(n2);
			tree.get(n2).add(n1);
		}
		
		
		dfs(1,0, 1);
			
		int M = Integer.parseInt(br.readLine());
		
		for(int i=0; i<M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " " );
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			int result = solve(n1, n2);
			System.out.println(result);
		}
	}
	
	
	public static void dfs(int a, int b, int count) {
		
		if(!visit[a]) {
			visit[a] = true;
			depth[a] = count ;
			parents[a] = b;
			
			for(int i=0; i<tree.get(a).size(); i++) {
				int next = tree.get(a).get(i);
				dfs(next, a, count+1);
			}
		}
	}
	
	
	public static int solve(int a, int b) {
	
		int depth1 = depth[a];
		int depth2 = depth[b];
		
		while(depth1 != depth2) {
			if(depth1> depth2) {
			
				a = parents[a];
				depth1--;
			}else {
				b = parents[b];
				depth2--;
			}
		}
	
		while(a!=b) {
			a= parents[a];
			b= parents[b];
		
		}
		
			return a;		
	}
}

 

3. 코드 설명

 

 

코드에서 사용된 메서드에 대해 설명하겠다.

1. dfs 메서드

 

트리 각 노드 부모노드는 parents 배열에 입력해준다.

level 값은 depth 배열에 입력해준다.

 

예를 들어 노드 6의 부모노드는 2, level은 3이므로,

parents[6] = 2, depth[6] = 3

 

2. solve 메서드

 

위에서 설명한 것처럼,

1) 6번 노드, 11번 노드의 level 값 (depth 배열 값)을 비교한다.

=> depth[6] = 3 < depth[11] = 4 

값이 더 큰 11번 노드와 관련해 변화를 준다.

 

2) 11번 노드의 부모 노드를 찾는다. => 5

5번과 6번 노드의 level 값을 비교한다.

depth[5] = depth[6] = 3

 

3) 3으로 값이 같으므로 5번, 6번 노드의 부모노드가 같은지 확인한다.

부모 노드가 같으면, 최종 정답이 된다. => 즉 가장 가까운 공통 조상

부모 노드가 모두 2이므로 정답이다.

 

참고 블로그 :

https://loosie.tistory.com/360

[BOJ] 백준 11437번 LCA (Java)