공부 기록

2020/07/15 - [알고리즘 공부] - boj 11437: LCA

두 정점간의 거리는 LCA를 사용해서 구할 수 있다.

먼저 LCA를 구한 뒤, LCA까지의 거리를 모두 더하면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		int[] distances = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Node> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Node>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			int distance = in.nextInt();
			pair[node1].add(new Node(node2, distance));
			pair[node2].add(new Node(node1, distance));
		}

		depth = calculateNodeDepth(pair, parentNode, distances, n);

		int test = in.nextInt();

		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];
			int distance = 0;

			if (depth1 < depth2) {
				int tmp = node1;
				node1 = node2;
				node2 = tmp;

				depth1 = depth[node1];
				depth2 = depth[node2];
			}

			distance = calculateLCA(parentNode, depth, distances, node1, node2);
			System.out.println(distance);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int distance[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 0;

		while (depth1 > depth2) {
			ans += distance[node1];
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			ans += distance[node1];
			ans += distance[node2];
			node1 = parent[node1];
			node2 = parent[node2];
		}
		
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Node> pair[], int parent[], int distance[], int n) {
		Queue<Node> queue = new LinkedList<Node>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(new Node(1, 0));
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			Node node = queue.poll();

			for (Node i : pair[node.name]) {
				if (!isVisited[i.name]) {
					queue.add(i);
					depth[i.name] = depth[node.name] + 1;
					parent[i.name] = node.name;
					distance[i.name] = i.distance;
					isVisited[i.name] = true;
				}
			}
		}
		return depth;
	}
}

class Node {
	int name;
	int distance;

	public Node(int name, int distance) {
		this.name = name;
		this.distance = distance;
	}
}

LCA: Lowest common Ancestor

두 노드의 가장 가까운 공통 조상을 찾는 문제이다.

LCA를 찾기 위해서는 두 노드의 level과 부모를 알아야한다.

따라서

• 두 노드의 레벨이 다르면, 레벨이 같을 때까지 레벨이 큰 것을 한 칸씩 위로 올린다.
• 두 노드의 레벨이 같아지면, 같은 노드가 될 때까지 한 칸씩 위로 올린다.

인접 행렬을 사용하면 메모리 초과가 생기고,

Queue에 pair을 저장하면 나중에 bfs를 돌 때 시간 초과가 생기므로

LinkedList의 배열에  pair을 저장하고 바로 꺼내 쓸 수 있도록 한다.

이 문제의 주의할 점은 입력 시 어떤 노드가 parent이고 어떤 노드가 child인지 알 수 없으므로

bfs을 돌 때 parent와 child를 정의할 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Integer> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			pair[node1].add(node2);
			pair[node2].add(node1);
		}

		depth = calculateNodeDepth(pair, parentNode, n);

		int test = in.nextInt();
		int ans = 1;
		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];

			if (depth1 < depth2) {
				ans = calculateLCA(parentNode, depth, node2, node1);
			} else{
            	ans = calculateLCA(parentNode, depth, node1, node2);
            }
			System.out.println(ans);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 1;

		while (depth1 > depth2) {
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			node1 = parent[node1];
			node2 = parent[node2];
		}

		ans = node1;
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Integer> pair[], int parent[], int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(1);
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			int node = queue.poll();

			for (int i : pair[node]) {
				if (!isVisited[i]) {
					queue.add(i);
					depth[i] = depth[node] + 1;
					parent[i] = node;
					isVisited[i] = true;
				}
			}
		}
		return depth;
	}
}