(백준) 망가진 나무 _ 24232

https://www.acmicpc.net/problem/24232

 

🐢 설명

트리 DP 문제인데 dfs 활용이 필요한 문제이다.

 

처음에 어떻게 접근해야 하는지 머리를 오래 싸맸는데 결국 풀지 못해서 다른 풀이를 참고했다. 결론은 총 3번의 dfs를 통해 문제를 풀게 된다.

 

먼저 간선 정보를 이용해서 트리를 만들어야 하는데 이때 간선은 목적지, IN/OUT 구분값, 나중에 출력을 위한 번호 까지 총 3개의 변수를 들고 있어야 한다. 또한 주어진 정방향 간선을 adj[u].add(v) 와 같이 넣어줬다면 반대도 adj[v].add(u)를 넣어줘야 한다. 물론 위에서 말한 3가지 변수를 함께 채워서

 

트리를 만들었다면 어떤 노드에서 다른 모든 노드로 가는데 최소 비용이 드는지 알기위한 dfs를 돌려야 하는데 이게 한번에 안된다. 3번의 dfs로 나눠서 풀게 된다.

 

1번 dfs : 특정 노드 x를 잡고 해당 노드가 모든 정점에 도달하는데 필요한 간선 전환 비용을 구한다.

• dfs를 돌면서 인접 노드들에 대한 간선 정보를 보고 IN/OUT에 따라서 비용을 1 더하거나 안더하면 된다.
• 예를들어 x번 노드과 인접노드 x1 사이의 간선이
  OUT이면 dp[x] = x1이 루트인 서브트리에서의 비용 + 0 이되고,
  IN (역방향)이면 돌려야 하므로 dp[x] = x1이 루트인 서브트리에서의 비용 + 1이 된다.
• x1이 루트인 서브트리에서의 비용은 dfs (x1)으로 구하면 되므로, 간선 방향에 따른 "+1" 만 잘해주면 된다.

2번 dfs: 특정 노드 x의 비용을 가지고 다른 노드들에 대해서 조건에 맞기위한 비용을 구한다.

 

x 노드의 인접노드 x1이 있을 때, x1이 리프노드라고 가정해보자. 그러면 x1 의 조건에 필요한 비용은 얼마가 될까?

• 만약 x <- x1 간선이라면, x가 필요한 비용보다 오히려 1이 적을 것이다. 간선이 OUT이므로 따라서 dp[x1] = dp[x] - 1 이된다.
• 만약 x -> x1 간선이라면, x가 필요한 비용은 1이 더 필요하게 될것이다. 간선이 IN 이므로 돌려줘야 하기 때문이다. 따라서 dp[x1] = dp[x] + 1이 된다.

이런식으로 다른 노드들도 똑같이 dfs를 돌려주면서 구하면 된다.

 

3번 dfs : 2번 dfs를 통해 모든 노드들에서의 전환비용을 구했으므로 최소 비용이 드는 노드를 찾고, 해당 노드를 기준으로 마지막 dfs를 돌린다.

• 이때, 간선마다 달아준 번호를 사용해서 배열의 인덱스로서 방향이 OUT이면 0을 넣고, IN이면 전환비용 1을 넣어준다.

🐢코드

package 트리DP;

import java.util.*;
import java.io.*;

/*
5
2 4
2 3
3 1
5 1
 */
public class 망가진나무_24232 {
	static int N;
	static ArrayList<Node> adj[];
	static int[] dp;
	static boolean[] visited;
	static int IN = 1, OUT = 0;
	static int[] reverseArr;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		dp = new int[N + 1];
		adj = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		for (int i = 0; i < N + 1; i++) {
			adj[i] = new ArrayList<>();
		}
		reverseArr = new int[N + 1];

		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			adj[u].add(new Node(v, OUT, i + 1));
			adj[v].add(new Node(u, IN, i + 1));
		}

		dp[1] = dfsOne(1);

		Arrays.fill(visited, false);
		visited[1] = true;
		for (Node next : adj[1]) {
			dfsOthers(1, next.here, next.dir);
		}

		int min = Integer.MAX_VALUE;
		int minNode = 0;
		for (int i = 1; i < N + 1; i++) {
			int cost = dp[i];
			if (cost < min) {
				min = cost;
				minNode = i;
			}
		}

		Arrays.fill(visited, false);
		dfsMin(minNode);

		StringBuilder ret = new StringBuilder();
		for (int i = 1; i < N; i++) {
			ret.append(reverseArr[i]);
		}
		System.out.println(ret);
	}

	private static void dfsMin(int root) {
		visited[root] = true;

		for (Node next : adj[root]) {
			if (visited[next.here]) continue;

			dfsMin(next.here);

			reverseArr[next.num] = next.dir;
		}
	}

	private static void dfsOthers(int from, int to, int dir) {
		visited[to] = true;

		if (dir == IN) {
			dp[to] += dp[from] - 1;	// to 에서는 바로 갈 수 있으므로 비용 - 1
		} else if (dir == OUT) {
			dp[to] += dp[from] + 1; // to 에서는 역으로 뒤집는 비용 + 1
		}
		for (Node next : adj[to]) {
			if (!visited[next.here]) {
				dfsOthers(to, next.here, next.dir);
			}
		}
	}

	private static int dfsOne(int root) {
		visited[root] = true;
		int ret = 0;

		for (Node next : adj[root]) {
			if (!visited[next.here]) {
				ret += dfsOne(next.here) + next.dir; // 역방향은 비용 + 1
				// 예를들어 1 -> 3은 역방향이므로 (3이 루트인 서브트리에서의 최대 비용) + (1 <- 3 비용 1)
			}
		}
		return ret;
	}

	private static class Node {
		int here;
		int dir;
		int num;

		public Node(int here, int dir, int num) {
			this.here = here;
			this.dir = dir;
			this.num = num;
		}
	}
}

🐢 마무리

dfs를 여러번 사용하여 풀수있다라는 생각을 가져야 겠다.