공부 기록

k진 트리에서 두 노드 사이의 거리를 구하는 문제이다.

공통 조상문제와 유사한데, 각 노드에서 공통 조상까지의 거리를 구한 뒤 더하면 된다.

주의할 점은 노드의 수가 10^15이므로 long 타입을 사용해야 한다.

이때 k == 1인 경우는 트리의 높이가 log단위가 아니고 한 개로 쭉 나열 되어 있으므로 따로 먼저 높이 차를 리턴해주면 된다.

​

k진 트리를 보면서 규칙을 찾아보자

정점 long A의 부모노드가 (A-2)/k + 1임을 알 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long n = in.nextLong(); // 노드 수
		int k = in.nextInt(); // k진 트리
		int test = in.nextInt();

		for (int t = 0; t < test; t++) {
			long x = in.nextLong();
			long y = in.nextLong();

			if (k == 1) {
				System.out.println(Math.abs(x - y));
				continue;
			}

			long distance = 0;
			while (x != y) {
				long max = Math.max(x, y);
				y = Math.min(x, y);
				x = (max - 2) / k + 1;
				distance++;
			}
			System.out.println(distance);
		}
	}
}

2021/01/17 - [알고리즘 공부] - SWEA 1248: 공통조상

이 문제는 트리를 어떤 방식으로든 순회했을 때, 그 합의 최대를 구하는 문제이다.

예를 들어 위 예제의 경우 최적의 순회 방법중 하나는 15 -> 20 -> 7 이고 그 합은 15 + 20 + 7 = 42이다.

먼저 저번에 공부했던 tree dp처럼 어떤 노드를 기준으로 해당 서브 트리의 최대값을 구할 수 있도록 하자고 생각했다.

즉, 리프 노드의 경우는 해당 노드에 적혀있는 수를 리턴하고,

그 이외는 아래에서부터 올라오면서 최대 값을 해당 노드에 저장하는 식이다.

이러한 경우 시간복잡도는 O(N)으로 볼 수 있으며 풀이는 아래와 같다.

class Solution {
	int answer = Integer.MIN_VALUE;

	public int findMaxNode(TreeNode node) {
		if (node == null) {
			return 0;
		}

		int leftValue = Math.max(findMaxNode(node.left), 0);
		int rightValue = Math.max(findMaxNode(node.right), 0);

		int newValue = node.val + leftValue + rightValue;

		answer = Math.max(answer, newValue);

		return node.val + Math.max(leftValue, rightValue);
	}

	public int maxPathSum(TreeNode root) {
		findMaxNode(root);
		return answer;
	}
}

문제 조건

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

이 문제의 경우는 우수 마을에 포함할지 말지 모두 구한 후 조건에 맞는지 확인하는 방식으로 푼다면 O(2^N)으로 시간초과가 날 것이다.

'우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. => DP를 사용하면 될 것 같다.

우수마을의 경우 트리 형태이고, 이 트리에서 DP를 사용해서 문제를 풀어야 한다.

이 문제에선, 부모 노드를 우수 마을에 포함할 경우, 자식노드는 우수 마을에 포함하면 안된다.

그리고 일반 마을이 부모 노드일 경우, 자식 노드에는 우수 마을이 있어야 한다.(합을 최대로 구해야 하니까)

dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값

아무 노드나 루트로 삼고 DFS를 진행한다. => 1로 시작하자

왜냐면 조건중에

나라는 트리(Tree) 구조로 이루어져 있으며, 즉 마을과 마을 사이를 직접 잇는 N-1개의 방향 없는 길이 있으며,

모든 마을은 연결되어 있다. 는 조건이 있기 때문이다.

이 문제에서 주어진 문제는 방향이 없는 연결을 가지는 트리이며, 모든 노드가 루트 노드가 될 수 있다.

DFS를 사용한 이유는 순회를 하면서 우수마을 조건에 포함하고 포함하지 않는 식의 백트래킹을 이용하기 위해서이다.

리프노드에 도달하게 되면,

노드 5와 같이 다시 거슬러 올라오면서 dp값을 채우도록 한다.

노드 2까지 올라오면 다른 분기점으로 내려가면서

마찬가지로 방문하지 않은 노드까지 찾아내려간다.

결론적으로 업데이트된 dp의 최종 결과는 아래와 같다.

그리고 이를 적용한 코드는 아래와 같다

import java.util.*;

public class Main {
	public static int max = 0;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int people[] = new int[n + 1];
		LinkedList<Integer> connections[] = new LinkedList[n + 1];

		for (int i = 1; i <= n; i++) {
			people[i] = in.nextInt();
			connections[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			connections[a].add(b);
			connections[b].add(a);
		}

		/*
		 * dp[i][0]: i번 마을이 우수 마을이 아니었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값,
		 * 
		 * dp[i][1]: i번 마을이 우수 마을이었을 때 i번 마을을 루트로 하는 서브 트리의 우수 마을들 인구수의 최댓값
		 * 
		 */
		int dp[][] = new int[n + 1][2];
		boolean isVisited[] = new boolean[n + 1];
		int start = 1;
		dfs(start, isVisited, people, dp, connections);

		System.out.println(Math.max(dp[start][0], dp[start][1]));
	}

	public static void dfs(int root, boolean[] isVisited, int[] people, int[][] dp, LinkedList<Integer> connections[]) {
		isVisited[root] = true;
		for (int next : connections[root]) {
			if (!isVisited[next]) {
				dfs(next, isVisited, people, dp, connections);
			}
		}
		dp[root][0] = 0;
		dp[root][1] = people[root];
		for (int next : connections[root]) {
			dp[root][0] += Math.max(dp[next][0], dp[next][1]);
			dp[root][1] += dp[next][0];
		}
	}
}

주의할 점은 top down방식으로 dp를 업데이트 하게 되면 분기점 등에서 겹치는 값이 생길 수 있으므로

botton up 방식으로 값을 업데이트 하도록 해야 한다.