[백준 11437번][Java] LCA - 최소 공통 조상 찾기

www.acmicpc.net/problem/11437

11437번: LCA

트리 구조의 특성을 생각해보면 풀이를 떠올릴 수 있다.

트리 구조에서 하나의 노드는 다수의 자식을 가질 수 있지만 부모 노드를 오직 하나만 가진다.

그렇기 때문에 각 노드에서 부모 노드의 참조를 저장해두면 두 개의 노드에서 따라올라가면서 최소 공통 조상을 찾을 수 있다.

 

까다로운건 이 문제에서 입력으로 트리를 구성하기 위해서는 일단 양방향 노드 그래프를 만들어야 되는데, 

나는 그냥 한번 임시 트리를 만들고나서 다시 트리를 구성해서 해결했다. 이 과정 중에 depth도 계산해 저장해두자. 

 

공통 조상을 찾을 땐 우선 두 노드의 최소 depth까지 이동해 depth를 동일하게 해주자.

동일하게 해주는게 비교하기 편하다. 그리고 이 과정 중에 두 노드 중에 공통 조상이 되는 경우도 잡을 수 있다. 

 

트리를 다시 구성해서 그런지 꽤 느리다.

2초 정도 나오는데 어차피 제한은 3초니까 뭐... 

 

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

/*
LCA
https://www.acmicpc.net/problem/11437
 */
public class Main {
	static int n,m;
	static Node[] modifiedTree, nodes;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		nodes = new Node[n]; //임시 트리
		for (int i = 0; i < n; i++) { nodes[i] = new Node(i);}
		for (int i = 0; i < n-1; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(st.nextToken())-1;
			int v = Integer.parseInt(st.nextToken())-1;
			nodes[u].children.add(v);
			nodes[v].children.add(u);
		}

		modifiedTree = new Node[n];
		restructTree();

		m = reader.readInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(st.nextToken())-1;
			int v = Integer.parseInt(st.nextToken())-1;
			sb.append(findLCA(u,v) + "\n");
		}
		sb.deleteCharAt(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static int findLCA(int u, int v) {
		int u_depth = modifiedTree[u].depth;
		int v_depth = modifiedTree[v].depth;
		int minDepth = Math.min(u_depth, v_depth);
		//depth 동일하게 맞추기
		u = getAncestor(u, u_depth-minDepth);
		v = getAncestor(v, v_depth-minDepth);

		if(u == v) return u+1;
		else {
			while(u != -1) {
				u = modifiedTree[u].parentId; v = modifiedTree[v].parentId;
				if(u == v) break;
			}
			return u+1;
		}
	}
	//노드의 id에서 go만큼 부모로 이동하고 인덱스를 반환한다.
	private static int getAncestor(int id, int go) {
		for (int i = 0; i < go; i++) {
			id = modifiedTree[id].parentId;
		}
		return id;
	}

	private static void restructTree() {
		Queue<Integer> q = new ArrayDeque<>();
		boolean[] discovered = new boolean[n];

		for (int i = 0; i < n; i++) {
			modifiedTree[i] = new Node(i);
		}

		q.add(0);
		discovered[0] = true;

		while(!q.isEmpty()) {
			Node here = nodes[q.poll()];

			for (int i = 0; i < here.children.size(); i++) {
				int childId = here.children.get(i);

				if(!discovered[childId]) {
					modifiedTree[here.id].children.add(childId);
					modifiedTree[childId].parentId = here.id;
					modifiedTree[childId].depth = modifiedTree[here.id].depth+1;
					discovered[childId] = true;
					q.add(childId);
				}
			}
		}
	}
}
class Node {
	int id, depth, parentId;
	List<Integer> children = new ArrayList<>();
	public Node(int id) {
		this(id, -1, 0);
	}
	public Node(int id, int parentId, int depth) {
		this.id = id;
		this.parentId = parentId;
		this.depth = depth;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}