1248. 공통조상

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD

SW Expert Academy

 

분류

트리

LCA 알고리즘

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

LCA 알고리즘을 통해 공통 조상을 찾으면 된다.

 

시행착오

없음

 

코드

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

class Solution{
	static Node[] tree;

	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int tc = 1; tc <= T; ++tc){
			String[] arr = br.readLine().split(" ");
			int N = Integer.parseInt(arr[0]), E = Integer.parseInt(arr[1]), V1 = Integer.parseInt(arr[2]), V2 = Integer.parseInt(arr[3]);
			tree = new Node[N + 1];
			arr = br.readLine().split(" ");

			for (int i = 0; i < E; i++){
				int v1 = Integer.parseInt(arr[i * 2]), v2 = Integer.parseInt(arr[i * 2 + 1]);

				if (tree[v1] == null) tree[v1] = new Node(v1, -1);
				if (tree[v2] == null) tree[v2] = new Node(v2, -1);

				tree[v1].children.add(v2);
				tree[v2].parent = v1;
			}

			tree[1].setDep(1);

			if (tree[V1].dep > tree[V2].dep){ //V2가 더 깊어야 함
				int tmp = V1;
				V1 = V2;
				V2 = tmp;
			}

			while (tree[V1].dep != tree[V2].dep) {
				V2 = tree[V2].parent;
			}

			while (V1 != V2) {
				V1 = tree[V1].parent;
				V2 = tree[V2].parent;
			}

			System.out.println("#" + tc + " " + V1 + " " + tree[V1].cnt);
		}
	}

	public static class Node{
		int v, dep = 0, parent, cnt = 0;
		List<Integer> children = new ArrayList<Integer>();

		public Node(int v, int parent){
			this.v = v;
			this.parent = parent;
		}

		public int setDep(int dep){
			this.dep = dep;
			int cnt = 1;

			for (int i = 0; i < children.size(); i++){
				cnt += tree[children.get(i)].setDep(dep + 1);
			}

			this.cnt = cnt;

			return cnt;
		}
	}
}