[백준] Gold3 - 1808 숌작업
백준 1808 숌작업
문제
주어진 트리에 대해 아래와 같은 연산을 진행하여 트리의 레벨을 줄일 수 있다.
- 루트가 아닌 정점 V를 선택한다.
- V의 조상중 하나인 정점 U를 선택한다.
- V와 V의 부모를 이은 간선을 제거한다.
- U에서 V로 간선을 이은다. U는 V의 부모가 된다.
- 노드의 수 N이 첫 줄에 주어진다.
- 다음 N-1줄 동안 노드 간의 연결 관계가 주어진다. a b 형태이며 a노드가 b노드의 부모이다.
- 마지막 줄에 달성하고자 하는 최소 레벨 H가 주어진다.
- 이 때 주어진 트리를 높이 H로 만드는데 최소 비용을 구하라.
해설
이 문제는 Greedy 알고리즘으로 해결하면 그렇게 어려운 문제는 아니었다. 이 문제를 따로 포스트 하는 이유는 이 문제를 Dynamic Programming으로 해결하는 방법을 기록하기 위해서이다.
어떤 방식을 선택하더라도 반드시 파악해야하는 점은 어떤 루트가 아닌 노드 W가 있고, W의 임의의 조상 V가 있다고 할 때, V를 루트로 하는 서브 트리를 연산을 통해 레벨을 감소시키면, W 역시 그 레벨이 같이 감소한다는 것이다.
주어진 예제 입력 1번에 대해 생각해보자. 그래프는 아래 그림과 같이 나타날 것이다
이 그림에서 2번 노드에 대해 연산을 진행하고 선조 노드 0번 노드를 선택하면 아래 그림과 같이 변화한다.
한번의 연산을 통해 전체 그래프의 레벨을 1 감소시킨 것을 확인할 수 있다. 이 점을 유념하면서 Dynamic Programming 을 적용해보자
동적 계획법
문제의 입력을 받아 기본적인 그래프를 구성하는 함수를 작성한다.
class Solution {
int nrNode;
Map<Integer, List<Integer>> graph = new HashMap<>();
int H;
int dp[][];
...
void init() {
BufferedReader reader=...;
N = Integer.parseInt(reader.readLine());
for(int i = 0 ; i < N - 1 ; i++) {
String[] s = reader.readLine().split();
int from = Integer.parseInt(s[0]);
int to = Integer.parseInt(s[1]);
List<Integer> child = graph.getOrDefault(from, new ArrayList<>());
child.add(to);
graph.put(from, child);
}
H = Integer.parseInt(reader.readLine());
}
}
우선 메모이제이션을 위한 2차원 배열을 선언한다
int [][]dp = new int[노드의 수][최대 가능 레벨];
for(int i = 0 ; i < dp.length ; i++) {
Arrays.fill(dp[i], -1);
}
여기서 dp 배열은 다음과 같은 값을 나타낸다.
// dp[i][j] => 현재 레벨이 j이고, 루트가 i인 서브트리를 레벨 H로 만드는데 들어가는 최소 비용.
그 다음으로 숌 연산 비용을 구할 수 있는 재귀함수 cost(index, height) 를 정의한다.
private int cost(int index, int height) {
// 이 함수는 index 번째 노드를 루트로 하고, index의 현재 레벨이 height 인
// 서브트리의 높이를 H로 만드는데 필요한 비용을 반환한다.
// 비용 값은 dp[index][height]에 메모이제이션 된다.
...
if(dp[index][height] != -1) {
return dp[index][height];
}
return dp[index][height];
}
자 이제 각 서브트리의 탐색 조건을 어떻게 분기 시켜야하는지 살펴보자
a. 현재 탐색 리벨이 0이라면 전체 그래프의 최상단이며, 이 트리는 선택 자체가 불가능하다.
그렇기 때문에 곧바로 자식트리로 탐색을 진행한다.
b. 현재 레벨이 H와 동일하다면 현재 노드에 대해 연산을 진행함으로써 자식 노드들이 구성하는 각 서브 트리의 레벨을 한번에 낮출 수 있다.
c. 그 외의 경우에는 현재 노드에 연산을 진행하는 경우와, 자식 노드들에 대해서만 연산을 진행하는 경우로 나눌 수 있다.
위 조건을 그림으로 살펴보자
현재 인덱스의 노드가 루트라면 연산 자체를 진행할 수 없기 때문에 그림 상 분홍색으로 표기된 노드들로 구성된 서브 트리에 대해서만 연산이 가능하다. 이걸 식으로 풀어쓰면 아래와 같다.
ret += cost(child, height+1);
현재 인덱스의 노드의 레벨이 목표와 동일하다면, 해당 노드에 연산을 진행하여 오른쪽 트리와 같이 자식 노드들이 구성하는 서브트리의 레벨을 낮출 수 있다.
이 경우에는 자기 자신에 대해 연산을 진행하여 서브트리의 높이를 낮추는 비용(우측 상단 트리)과 자식들이 자신과의 연결을 끊고 현재 노드의 부모 노드와 연결하는 비용(우측 하단 트리)의 합 중 작은 것을 취해야 한다.
이제 이 조건을 코드로 옮겨보자
private int cost(int index, int height) {
...
List<Integer> childrens = graph.getOrDefault(index, null);
int ret = Integer.MAX_VALUE;
for(int child : childrens) {
if(height == 0) {
// 조건 a. 현재 노드의 레벨이 0인 경우
// 이 노드는 연산을 진행할 수 없기 때문에 자식 노드의 연산 비용이 자신의 비용이다.
ret += cost(child, h+1);
}else if(height == H) {
// 조건 b. 현재 노드의 레벨이 타겟 레벨과 같다면
// 현재 노드에 대해 연산을 진행하여 자식들의 서브 트리 높이를 1 낮춘다.
ret += cost(child, h) + 1; // 1은 현재 노드에서 진행한 연산 비용
} else {
// 조건 c. 현재 노드에 대해 연산을 진행하는 경우와, 자식 노드들을 현재 노드의 부모에
// 연결하는 비용을 합한 것중 작은 값을 취한다.
ret += min( cost(child, h) + 1, cost(child, h+1) );
}
}
dp[index][height] = ret;
return dp[index][height];
}
전체 소스 코드
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
public class Main {
public static class Solution {
int nrNode;
Map<Integer, List<Integer>> graph = new HashMap<>();
int[][] dp;
int H;
private void init() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
nrNode = Integer.parseInt(reader.readLine());
for(int i = 0 ; i < nrNode-1 ; i++) {
String[] nums = reader.readLine().split(" ");
int from = Integer.parseInt(nums[0]);
int to = Integer.parseInt(nums[1]);
List<Integer> connection = graph.getOrDefault(from, new ArrayList<>());
connection.add(to);
graph.put(from, connection);
}
H = Integer.parseInt(reader.readLine());
dp = new int[101][101];
for(int[] row : dp) {
Arrays.fill(row, -1);
}
}
private int cost(int index, int height) {
if(dp[index][height] != -1) {
return dp[index][height];
}
List<Integer> childrens = graph.getOrDefault(index, new ArrayList<>());
int ret = 0;
for(int child : childrens) {
if(height == 0) {
ret += cost(child, height+1);
} else if(height == H) {
// 현재 노드에 대해 연산한 값을 1 더해주고, 자식 노드로 탐색을 한다.
// 이 떄 자식 노드는 레벨이 1 낮아지므로 height 를 그대로 넘겨준다.
ret += cost(child, height) + 1;
} else {
// 현재 노드에 대해 연산한 경우의 비용과
// 현재 노드에 대해 연산을 하지 않은 경우 자식 노드의 서브트리에서 발생하는 비용을 합한 값의 최소값을 취한다.
ret += Math.min(cost(child, height) + 1, cost(child, height+1));
}
}
return dp[index][height] = ret;
}
public int run() throws IOException {
init();
return cost(0, 0);
}
}
public static void main(String[] args) throws IOException {
System.out.println(new Solution().run());
}
}
결과
후기
Dynamic Programming으로 풀 때 난이도가 굉장히 높아져서 굉장히 오래 분석했다. DP를 적용할 때 항상 점화식을 세우기 위한 문제 조건의 분석에 취약한 편이었는데 이 문제를 풀며 해당 부분의 약점을 보완해보고자 그림을 굉장히 많이 그렸었다. 부분 해법의 합이 전체의 정답으로 도출될 수 있다면 DP를 이용할 수 있는 것인데 이런 부분으로 분할하는데 좀 더 초점을 두고 연습할 필요를 느꼈다.