백준 양 구출 작전(16437)

axiom·2021년 5월 9일

양 구출 작전

1. 힌트

1) "각 섬에서 1번 섬으로 가는 경로는 유일", 섬들은 트리의 조건을 만족한다.

2) 모든 양이 살고 있는 섬에 대해서 루트까지 이동시키는 방법으로는 시간 초과를 피할 수 없다.

3) 트리의 재귀적인 성질을 이용하면 어떤 정점에 도착할 수 있는 양의 수를 구하고, 재귀적으로 나타낼 수 있다.

2. 접근

1) 문제를 분해할 수 있을까?

문제에서 "각 섬에서 1번 섬으로 가는 경로는 유일"하다고 했는데 어떻게 이 $N$ 개의 섬들이 트리임을 알 수 있을까?
트리는 모든 정점간의 경로가 유일한 그래프이다. 각 섬은 1번 섬으로 가는 경로가 존재하므로 1번 섬을 경유점으로 생각하면 모든 섬 간의 경로는 유일할 수 밖에 없다.

트리이기 때문에 어떤 임의의 정점을 잡고 루트라고 하여도 전혀 무리가 없다, 그렇기 때문에 우리는 1번 정점을 루트라고 하고, 모든 양들이 사는 섬에서 부모로 올라가는 간선을 따라 이동시켜볼 수 있다.

하지만 트리가 연결 리스트에 가깝게 이러한 모양으로 존재할 수도 있다. 이렇게 되면 모든 양을 이동시키는 시간 복잡도는 $O(N^2)$ 이다.
그렇다면 트리의 순회를 이용해서 한 정점은 한 번만 방문하게 하는 방법으로 풀 수 있도록 문제를 정의하여 보자

$f(n) =$ $n$ 번 정점에 도착할 수 있는 양의 수
이렇게 정의하면 $f(1)$ 이 우리가 구하고자 하는 값이 된다. $f(n)$ 의 값을 구하기 위해서는 $n$ 번 정점의 모든 자식들에 대해서 $f$ 값을 알아야 하는데 이는 트리의 중위 순회로 구현하면 모든 정점에 대해 한 번만 방분하여 $O(N)$ 의 시간 복잡도로 해결 가능하다.

3. 구현

public class Main {
	static int[] parent;
	static ArrayList<ArrayList<Integer>> children;
	static int[] amount;
	
	// here을 루트로 하는 서브트리에서 루트에 도착하고 살아남는 양의 수
	static long inorder(int here) {
		long sum = amount[here];
		for (int ch : children.get(here)) sum += inorder(ch);
		return Math.max(sum, 0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		parent = new int[N + 1]; parent[1] = 1;
		children = new ArrayList<>(N + 1);
		for (int i = 0; i < N + 1; i++) children.add(new ArrayList<>());
		amount = new int[N + 1];
		for (int i = 2; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			String t = st.nextToken();
			amount[i] = Integer.parseInt(st.nextToken());
			if (t.equals("W")) amount[i] *= -1;
			int p = Integer.parseInt(st.nextToken());
			parent[i] = p;
			children.get(p).add(i);
		}
		System.out.println(inorder(1));
	}
	
}

1) 시간 복잡도

$inorder$ 함수가 모든 정점에 대해서 한 번씩만 호출된다는 것은 명확하다. 하지만 자식들을 순회할 때 시간 복잡도는 어떻게 되는 것일까?
$inorder$ 함수를 얼마나 호출하던 간에 자식들에 대해서 순회하는 횟수는 트리에 존재하는 간선의 개수와 동일하다. 트리의 정점이 $N$ 개 이면 간선은 $N - 1$ 개 이므로 시간 복잡도는 $O(N + N - 1) = O(N)$ 이 된다.