[트리] 백준 3584번 가장 가까운 공통 조상 - JAVA

어제밤부터 고민하고 고민하던 문제!

이제는 그냥 외워야겠다라고 싶을 만큼 도전했다 ㅎㅎ..

 

 

---

1. 출처

---

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

3584번: 가장 가까운 공통 조상

 

 

 

---

2. 설계

---

처음에는 조상이라고 해서 크루스칼로도 생각해봤는데, 그건 찐 조상! 나의 최상위 조상을 찾아주는 알고리즘이기 때문에 아니라고 생각했다. 그 후에는 트리를 직접 만들어서 같은 두 노드를 같은 depth로 만들어 준 후 함께 올라가는 시나리오를 생각했었는데, 자식이 갖는 수가 이진트리처럼 일정하지 않아서 depth를 관리하기 쉽지 않았다.

 

 

1. 부모 자식 관계를 입력받으면서 "이 자식이 어떤 부모를 갖는지" 배열을 채워준다.

p = new int[N+1];
for(int i=1;i<=N-1;i++) {
	int pa = sc.nextInt();
	int c = sc.nextInt();

	p[c]=pa;
}

p[c] : 자식 c의 부모

pa : 지금 입력으로 들어온 부모

 

 

(개인적인 고민)

난 이 때 고민을 했던 것이 있다.

 

예시 중 

부모 3 - 자식 1

부모 1 - 자식 5

즉, 3 - 1 - 5

 

이 상태에서

부모 3 - 자식 5

이게 들어온다면, 5의 부모는 1이었다가 갑자기 3으로 바뀌는데, 영향은 없을 것인가?

 

즉, 3 - 1  /  3 - 5가 되는 것...!

 

근데 생각해보니 N-1개의 관계가 들어온다고 했고, 그 안에 자식 N-1개의 부모를 선정해줘야하기 때문에 "같은 자식이 2번 나올 일은 없다." 라고 이해가 되었다.

 

 

 

2. a노드 b노드를 입력받아 이 두 노드의 가장 가까운 공통 조상(LCA)를 찾아줄 것이다.

//두 노드를 받아 공통 부모를 갖는 이를 찾는다.
int a_node = sc.nextInt();
int b_node = sc.nextInt();

 

 

3. 그러기 위해서 a노드는 자기 자신부터 시작해 조상을 타고 올라가면서 visited를 true 처리 해준다.

public static void total_parent(int a_node) {

	int c = a_node;
	while(c!=0) {
		visited[c] = true;
		c=p[c];
	}
}

c = p[c] : 현재 나를 나의 부모로 바꿔준다.

 

 

 

4. b노드는 자기 자신부터 시작해 조상을 타고 올라가면서 visited에 true를 만나면 그 조상이 정답이다.

//같은 부모가 있는지 확인
public static int same_parent(int b_node) {
		
	int c = b_node;
	int result = 0;
		
	while(c!=0) {
		if(visited[c]) {
			result = c;
			break;
		}
		c = p[c];
	}
		
	return result;
		
}

 

 

 

백준 3584 가장 가까운 공통 조상 Java

 

이 분의 코드를 보면서 많이 배웠다.

 

 

 

---

3. 전체 코드

---

import java.util.Scanner;


public class Main {
	static int N;
	static int[] p;
	static boolean[] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int T=1;T<=t;T++) {
			N = sc.nextInt();//노드의 수 
			
			
			//N-1개의 노드로 tree를 만든다.
			p = new int[N+1];
			for(int i=1;i<=N-1;i++) {
				int pa = sc.nextInt();
				int c = sc.nextInt();
				
				p[c]=pa;
			}
			
			//두 노드를 받아 공통 부모를 갖는 이를 찾는다.
			int a_node = sc.nextInt();
			int b_node = sc.nextInt();
			

			//1. a_node의 전체 부모를 구해라 
			//a_parent_list에는 인덱스가 작을수록 a_node와 가까운 부모
			visited = new boolean[N+1];
			total_parent(a_node);
			
			
			//2. b_node의 부모를 추적하면서 같은 수가 있는지 확인 > 결과 출력 
			System.out.println(same_parent(b_node));

		}//test end
	}
	
	//전체 부모를 구해라
	public static void total_parent(int a_node) {

		int c = a_node;
		while(c!=0) {
			visited[c] = true;
			c=p[c];
		}
	}
	
	//같은 부모가 있는지 확인
	public static int same_parent(int b_node) {
		
		int c = b_node;
		int result = 0;
		
		while(c!=0) {
			if(visited[c]) {
				result = c;
				break;
			}
			c = p[c];
		}
		
		return result;
		
	}
}

 

 

---

 

 

끝!