[Baekjoon] 11437_LCA

Gold III

문제(출처: https://www.acmicpc.net/problem/11437)

---

< LCA >

 

문제 풀이 

 

루트는 1번이므로 1번부터 시작해서 각 정점까지의 깊이와 부모 정점을 구한다. 가장 가까운 공통 조상을 알고 싶은 쌍을 입력받으면 먼저 정점 깊이를 같은 깊이로 맞춘다. 깊이가 같다면 가장 가까운 공통 부모를 구한다.

 

 

 my solution (Java)

 

ver1.

가장 가까운 공통 부모를 구할 때 우선순위 큐를 사용해서 깊이가 깊은 것 먼저 부모를 찾는 방식으로 구했다. 이 경우 6992ms 시간이 걸렸다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main { // LCA
	static int depth[], n, parent[];
	static ArrayList<ArrayList<Integer>> arr;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		n = Integer.parseInt(bf.readLine());

		arr = new ArrayList<>();
		depth = new int[n + 1];
		parent = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			arr.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			arr.get(a).add(b);
			arr.get(b).add(a);
		}

		findDepth();

		int m = Integer.parseInt(bf.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			bw.write(findParent(a, b) + "\n");
		}
		bw.flush();
	}

	private static int findParent(int a, int b) {
		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() { // 정점 번호, 깊이

			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1] - o1[1];
			}
		});
		queue.add(new int[] { a, depth[a], -1 });
		queue.add(new int[] { b, depth[b], -2 });

		int aParent = a;
		int bParent = b;

		while (!queue.isEmpty()) {
			if (aParent == bParent) {
				break;
			}

			int info[] = queue.poll();

			int num = parent[info[0]];
			if (info[2] == -1) {
				aParent = num;
				queue.add(new int[] { num, depth[num], -1 });
			} else {
				bParent = num;
				queue.add(new int[] { num, depth[num], -2 });
			}
		}
		return aParent;
	}

	private static void findDepth() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);

		boolean visited[] = new boolean[n + 1];
		visited[1] = true;

		while (!queue.isEmpty()) {
			int info = queue.poll();
			for (int i = 0; i < arr.get(info).size(); i++) {
				if (!visited[arr.get(info).get(i)]) {
					visited[arr.get(info).get(i)] = true;
					parent[arr.get(info).get(i)] = info;
					depth[arr.get(info).get(i)] = depth[info] + 1;
					queue.add(arr.get(info).get(i));
				}
			}
		}
	}
}

 

최종 ver.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _11437_ { // LCA
	static int depth[], n, parent[];
	static ArrayList<ArrayList<Integer>> arr;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		n = Integer.parseInt(bf.readLine());

		arr = new ArrayList<>();
		depth = new int[n + 1];
		parent = new int[n + 1];

		for (int i = 0; i <= n; i++) {
			arr.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			arr.get(a).add(b);
			arr.get(b).add(a);
		}

		findDepth();

		int m = Integer.parseInt(bf.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			bw.write(findParent(a, b) + "\n");
		}
		bw.flush();
	}

	private static int findParent(int a, int b) {
		int aParent = a;
		int bParent = b;

		while (aParent != bParent) {
			if (depth[aParent] > depth[bParent]) {
				aParent = parent[aParent];
			} else if (depth[aParent] < depth[bParent]) {
				bParent = parent[bParent];
			} else {
				aParent = parent[aParent];
				bParent = parent[bParent];
			}
		}
		return aParent;
	}

	private static void findDepth() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);

		boolean visited[] = new boolean[n + 1];
		visited[1] = true;

		while (!queue.isEmpty()) {
			int info = queue.poll();
			for (int i = 0; i < arr.get(info).size(); i++) {
				int num = arr.get(info).get(i);
				if (!visited[num]) {
					visited[num] = true;
					parent[num] = info;
					depth[num] = depth[info] + 1;
					queue.add(num);
				}
			}
		}
	}
}

변수)
n : 노드의 개수
arr : 그래프
depth : 노드 깊이
parent : 노드 부모
m : 가장 가까운 공통 조상을 알고 싶은 쌍의 개수

 

트리 상에 연결된 두 정점을 입력받아 arr에 양방향으로 저장한다. findDepth 함수를 통해 루트부터 깊이와, 부모를 구한다. 가장 가까운 공통 조상을 알고 싶은 쌍의 개수를 입력받은 후 그 수만큼 쌍을 입력받아 findParent 함수를 통해 가장 가까운 공통 조상을 출력한다.

 

findDepth

queue에 루트 노드 1을 넣고 시작한다. 방문 배열도 선언하여 루트 노드를 방문처리한다.

queue가 빌 때까지 다음 과정을 반복한다.

1) queue poll

2) 그래프를 통해 연결된 노드 탐색

3) 아직 방문하지 않은 노드라면 방문 표시 및 깊이를 [현재 깊이+1]로 저장, 부모를 [다음 노드의 부모]=[현재 노드]로 저장, queue에 다음 노드를 저장한다.

 

findParent(노드 a, 노드 b)

a의 가장 가까운 공통 조상을 a로, b의 가장 가까운 공통 조상을 b로 초기화한다. 두 노드의 가장 가까운 공통 조상이 같아질 때까지 다음 과정을 반복한다.

1) a의 깊이가 더 크다면 깊이를 맞추기 위해 a의 부모를 업데이트한다.

2) b의 깊이가 더 크다면 깊이를 맞추기 위해 b의 부모를 업데이트한다.

3) a와 b의 깊이가 같다면 둘 다 부모가 같아질 때까지 업데이트한다.

a와 b의 가장 가까운 공통 조상을 찾았다면 값을 반환한다.

---

---