[JAVA]트리 색칠하기(BOJ-1693 [그래프,DP])

📂문제 설명

 

n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때마다 1, 2, …, n의 비용이 든다. 즉, i번 색깔로 한 개의 정점을 색칠하면 i만큼의 비용이 든다는 것이다.

또한 정점에 색칠을 할 때에, 주어진 트리 상에서 인접해 있는 서로 다른 두 정점은 서로 다른 색깔로 칠해져야 한다. 이를 만족하면서, 전체 정점들을 색칠하는데 드는 총 비용을 최소화 하려 한다. 최소 비용을 계산하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 정점 및 색깔의 개수 n(1≤n≤100,000)이 주어진다. 다음 n-1개의 줄에는 각 줄에 두 개의 정수로 주어진 트리 상에서 연결되어 있는 두 정점의 번호가 주어진다.

 

출력

첫째 줄에 최소 비용을 출력한다.

 

---

 

📂아이디어 및 알고리즘(문제 풀이)

• 문제 접근
  • 제일 먼저 생각할건 n개의 노드를 칠하는데 과연 몇 종류의 색이면 전부 칠할 수 있을까??
  • 결론은 n개의 노드를 칠하는데 대략 log2 n 종류의 색만 필요하게 된다. (밑에 증명)
  • S(n) : 각 색마다 색칠하는 비용이 다를 때, n개의 색칠로 표현할 수 있는 최대 노드 개수!
    • S(n)에는 root노드가 n(n의 색)이고 서브 트리로 1~(n-1)[1~n-1의 색] 구성되어 있다.
    • S(n) >= 1(root 노드) + S(1) + S(2) + ... + S(n-1) 이라는 수식을 얻을 수 있다.
    • S(1) = 1, S(2) = 2의 값을 통해 수학적 귀납법으로 풀게 되면 
    • S(n) >= 2^(n-1) 값을 얻을 수 있게 된다.
  • 결국은 S(18) >= 2^17 이고 이 값은 10만보다 크기 때문에 18가지 색으로 전부 색칠이 가능한걸 의미한다.
  • 이제 색칠할 때의 최솟값을 알았기 때문에 트리를 구성하면서 DP로 해결하면 된다.
• 문제 풀이
  • Arraylist<Arraylist<Integer>> list로 트리를 구성해주고 입력값을 바탕으로 간선 연결 정보를 등록해준다.
  • TreeTable에서 부모 노드값과 현재 노드값, 현재 노드 색값을 인자로 넣어준다.
    • 부모 노드값을 알기 때문에 list.get(현재 노드)를 순회할 때 위로 올라가지 못하도록 하였다.
    • 자식 노드를 next index로 할때 min에 최댓값을 넣고 부모 컬러를 제외한 색을 자식 노드의 서브트리로 탐색해준다.
    • 최초에 트리의 말단노드까지 이동하여 최소 컬러값을 넣고 Math.min(서브 트리, min)값을 비교하여 작은 값을 현재 노드 컬러값에 누적합을 시켜준다.
    • 마지막으로 자신의 컬러값을 더해주어 return 시켜주게 되면 최솟값을 구할 수 있다. 

📂소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
    static int MAX_color = 20;
    static int DP[][] =  new int[100004][MAX_color+1];; 
    static boolean choice[];
    static int Min = Integer.MIN_VALUE;
    
    // 4색 정리 : 모든 정점들을 겹치지 않게 4가지 색으로 전부 칠할 수 있다. (참고)
    
    //DP[root][0~17]를 채우는 함수. 만약 자식 중에 table_set함수를 수행하지 않은 것이 있다면 자식 먼저 table_set하도록 한다. 
    public static int Tree_table_set(ArrayList<ArrayList<Integer>> list,int par,int index,int color) {
		//D[i][color] : 나의 부모 색깔이 color일때 i 번째 node를 root로 하는 subtree 최솟값.
    	
    	if(DP[index][color]!=0) return DP[index][color]; //값을 취합하는 과정에서 거꾸로 가는것을 방지
    	for(int next : list.get(index)) {
    		if(next == par) continue;    //부모로는 못가게 막는다. 
    		int min = Integer.MAX_VALUE; //최솟값 정의 => 값은 최대 
    		
        	for(int i=1;i<=MAX_color;i++) {
        		if(i == color) continue;  //일단 부모 컬러는 제외 시킨다. 
        		int t = Tree_table_set(list,index,next,i); //서브트리 탐색
        					  //트리의 말단 노드까지 이동하고 최소 컬러 노드를 넣어준다.        		                                              
        		min = Math.min(min, t);  
        	}
        	DP[index][color] += min;	
    	}
    	
    	//말단 노드에 값을 넣어준다. 
    	DP[index][color] += color;
    	return DP[index][color]; //그 값을 리턴해준다.    	
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();		
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
	
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<>());
		}
		for(int i=0;i<n-1;i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			list.get(x).add(y);
			list.get(y).add(x); 
		}
		list.get(0).add(1);
		int result = Tree_table_set(list,-1,0,0);
		System.out.println(result);
	}
}

 

🔎출처

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

1693번: 트리 색칠하기