[백준/JAVA] 3584_가장 가까운 공통 조상

백준🔗

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

 

문제

 

 

간단 풀이

얼마 전 알고리즘 특강 수업에서 그래프를 다루면서 LCA(Lowest Common Ancestor, 최소 공통 조상) 풀이법에 대해 배웠다. 그래서 오늘은 백준에서 비슷한 문제를 찾아서 풀어봤다.

✅ SWEA 이용하시는 분들은 1248. 공통조상 문제도 함께 보시면 좋습니다~!

 

2개의 정점에 대해 1개의 최소 공통 조상(LCA)을 찾는 방법

1) 각각 정점의 조상들을 모두 찾기
2) 공통으로 있는 조상들 찾아서 그 중 가장 아래에 있는 것이 LCA

 

위의 방법이 이번 문제의 핵심이라고 생각한다.

위 방법의 시간복잡도는 1번 과정에서 2*O(N), 공통 조상을 찾는 데 O(N) 따라서 총 3*O(N) 만큼이 소요된다.

 

트리를 구성하는 데에는 '완전' 이진 트리라는 조건이 없기 때문에 배열의 인덱스를 이용해서 자식, 부모로 넘어가는 방법은 사용할 수 없다. 

따라서 Node 클래스를 구현해서 정점마다 자식, 부모에 대한 정보를 가지고 있도록 했다.

 

한 가지 주의할 점!

✨✨Integer끼리의 비교에는 equals 메서드를 사용해야 한다!!✨✨

처음에 ==를 사용해서 비교했다가 자꾸 오답이 나와서 어디가 문제인지 찾는 데 시간이 좀 걸렸다...

다음부터는 기억해두고 주의하도록 하자~~!!

 

코드

import java.io.*;
import java.util.*;

public class Main {
	static Node[] tree;
	static ArrayList<Integer> ancestor1, ancestor2;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(br.readLine()); // 노드 개수
			// 트리 초기화
			tree = new Node[N + 1];
			for (int i = 1; i <= N; i++) {
				tree[i] = new Node();
			}
			// 간선 정보 입력
			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()); // 자식
				tree[A].children.add(B); // A의 자식으로 B 추가
				tree[B].parent = A; // B의 부모로 A 지정
			}

			// 가장 가까운 공통 조상(LCA) 구할 두 노드
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());

			// 각각의 공통 조상들 구하기
			ancestor1 = new ArrayList<>();
			ancestor2 = new ArrayList<>();
			findAncestor(node1, ancestor1);
			findAncestor(node2, ancestor2);

			// 공통 조상들 중 마지막에 있는 것이 LCA
			int LCA = 0;
			for (int i = 0; i < Math.min(ancestor1.size(), ancestor2.size()); i++) {
				if (!ancestor1.get(i).equals(ancestor2.get(i))) // Integer끼리는 equals 비교!!
					break;
				LCA = ancestor1.get(i);
			}
			sb.append(LCA + "\n");
		} // testcase
		System.out.println(sb);
	}

	static class Node {
		List<Integer> children;
		int parent;

		public Node() {
			this.children = new ArrayList<>();
			this.parent = 0;
		}
	}

	static void findAncestor(int idx, ArrayList<Integer> ancestor) {
		int p = tree[idx].parent;
		if (p != 0) {
			findAncestor(p, ancestor);
		}
		ancestor.add(idx);
	}
}

 

참고 자료