[백준] 단계별로 풀어보기(단계:32, 트리에서의 동적 계획법,JAVA)2213번, 트리의 독립집합

문제 링크

2213번: 트리의 독립집합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

트리

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프(사이클 X)

트리 구조 - 위키백과, 우리 모두의 백과사전

 

동적계획법

동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여 반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

이 문제에 핵심은

1. 그래프에 대한 정보와 정점의 가중치가 주어집니다.

2. 최대 독립집합이란? 인접한 정점은 포함되지 않은 최대 가중치를 가진 정점의 집합!

3. 최대 독립집합에 가중치, 포함된 집합을 오름차순으로 출력해야 합니다.

 

입력받은 그래프 내용에 대해서 트리의 형태로 만들어주었습니다.

 

※저는 루트 노드를 1로 설정하고 트리를 만들었습니다.

 

DFS탐색을 응용하여 독립집합의 모든 경우를 구하였습니다.

 

DFS 탐색을 진행할 때 2가지로 나뉠 수 있습니다.

 

현재 탐색하는 정점을 포함할 때 : 다음 인접한 정점은 포함되지 않는다

 

.현재 탐색하는 정점을 포함하지 않을 때 : 다음 인접한 정점을 포함을 하는 경우, 안하는 경우

 

위 과정을 탐색할 때 메모이제이션을 이용하여 반복되는 연산을 최소화하였습니다.

 

메모이제이션의 값을 이용하여 최대 독립집합의 가중치를 구하였습니다.

 

재귀를 통해서 메모이제이션의 값과 우선순위 큐를 이용하여 최대 독립집합에 포함된 정점을 구하였습니다.

 

※우선순위 큐를 사용한 이유는 오름차순으로 정렬하기 위해서입니다.

 

 

예제입력1

 

그래프의 값을 트리의 형태로 만들기

 

루트 정점 1을 포함할 때 : 정점 2는 포함하지 않는다.

정점 2을 포함할 때 : 정점 2를 포함하거나 안해도 된다.

.....

 

위 과정을 DFS로 진행하면 최대 독립집합의 값을 구할 수 있습니다.

최대 독립집합의 가중치 : 140

 

최대 독립집합의 포함된 정점을 구할 때

 

루트 정점 1이 포함될 때 최대 독립집합이기 때문에 정점 1이 포함되었을 때 탐색을 진행하면 됩니다.

정점 1이 포함되었기 때문에 정점 2는 포함될 수 없습니다.

 

정점 2는 포함되지 않기 때문에 정점 3과 정점 6은 포함되거나 포함되지 않아도 되므로 더 가중치가 큰 것을 선택합니다.

 

정점 3은 포함되었을 때 가중치가 커서 포함되므로 정점4는 포함 될수 없습니다.

 

정점 5는 정점 4가 포함되거나 포함되지 않아도 상관없지만 포함된 가중치가 더 크기 때문에 포함됩니다.

 

정점 7은 정점 6이 포함되거나 포함되지 않아도 상관없지만 포함된 가중치가 더 크기 때문에 포함됩니다.

 

포함된 정점 : 1, 3, 5, 7

 

※탐색할 때는 정렬이 되지 않을 수도 있으니 PriorityQueue를 이용하여 저장한 뒤 결과로 출력하여 오름차순으로 정렬되도록 하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 그래프에 대한 정보를 저장합니다.
• 루트 정점 1로 하는 트리를 만드는 buildTree함수를 실행하였습니다.
• DFS와 메모이제이션을 이용하여 최대 독립집합을 구하는 search함수를 실행하였습니다.
• 최대 독립집합의 포함된 정점을 구하는 재귀함수 trace함수를 실행하였습니다.
• BufferedWriter에 최대 독립집합의 가중치와 오름차순 정렬된 정점들을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• buildTree함수는 주어진 그래프를 트리의 형태로 만드는 함수입니다.
• search함수는 DFS와 메모이제이션을 이용하여 독립집합들을 비교하여 최대 독립집합을 구하는 함수입니다.
• trace함수는 메모이제이션, 우선순위 큐, 재귀를 이용하여 최대 독립집합의 정점들을 오름차순으로 구합니다.

 

결과 코드

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

public class Main{
	static int n;
	static int[] weight;	//가중치 저장 배열
	static int[][] DP;		//메모이제이션 배열
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//그래프 저장 리스트
	static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();	//트리 저장 리스트
    	//최대 독립집합의 포함된 정점을 오름차순으로 출력하기 위한 우선순위 큐
	static PriorityQueue<Integer> queue = new PriorityQueue<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		n = Integer.parseInt(br.readLine());
		weight = new int[n+1];
		DP = new int[n+1][2];
		for(int i=0;i<=n;i++) {
			graph.add(new ArrayList<>());
			tree.add(new ArrayList<>());
		}

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
        	//가중치 저장
		for(int i=1;i<=n;i++)
			weight[i] = Integer.parseInt(st.nextToken());
		
        	//입력되는 그래프 저장
		for(int i=0;i<n-1;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		buildTree(1, 0);	//루트 정점 1로 하는 트리 만들기
		
		int result = 0;
		int rootInclude = search(1, 1);	//루트 정점 1이 포함될 때 최대 독립집합
		int rootNonInclude = search(1, 0);	//루트 정점 1이 포함되지 않을 때 최대 독립집합
		if(rootInclude > rootNonInclude) {	//루트 정점 1이 포함된 독립집합이 클 때
			result += rootInclude;
			trace(1, 1);		//해당 독립집합에 포함된 정점 탐색
		}else {		//루트 정점 1이 포함되지 않은 독립집합이 클 때
			result += rootNonInclude;
			trace(1, 0);		//해당 독립집합에 포함된 정점 탐색
		}
		bw.write(result + "\n");		//가중치 BufferedWriter 저장
		while(!queue.isEmpty())		//정점들 BufferedWriter 저장
			bw.write(queue.poll() + " ");
		
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//메모이제이션, 우선순위 큐를 이용해 독립집합에 포함된 정점 탐색하는 재귀함수
	static void trace(int cur, int check) {
		if(check==1) {		//현재 정점 포함
			queue.add(cur);
            		//인접한 정점 미포함
			for(Integer next : tree.get(cur)) {
				trace(next,0);
			}
		}else {		//현재 정점 미포함
        		//인접한 정점에서 가중치가 더 큰 포함되거나 포함되지 않을 때 선택
			for(Integer next : tree.get(cur)) {
				if(DP[next][1] > DP[next][0]) {
					trace(next, 1);
				}else
					trace(next, 0);
			}
		}
	}
    	//DFS와 메모이제이션으로 최대 독립집합 구하는 함수
	static int search(int cur, int check) {
		int result = 0;
        	//이미 탐색해본 정점일 때
		if(DP[cur][check]!=0) {
			return DP[cur][check];
		}

		//현재 정점 포함시
		if(check == 1) {
			result += weight[cur];
            		//인접한 정점 미포함
			for(Integer next : tree.get(cur))
				result += search(next, 0);
		}else {		//현재 정점 미 포함시
			for(Integer next : tree.get(cur)) {
				int include = search(next, 1);	//인접한 정점 포함할 때
				int nonInclude = search(next , 0);	//인접한 정점 미포함할 때
                		//가중치가 더 큰 것을 선택
				if(include > nonInclude) {
					result += include;
				}else
					result += nonInclude;
			}
		}
		return DP[cur][check] = result;
	}
    	//그래프에 대한 내용으로 트리 만드는 함수
	static void buildTree(int cur, int root) {
		for(Integer next : graph.get(cur)) {
			if(next != root) {
				tree.get(cur).add(next);
				buildTree(next, cur);
			}
		}
	}
}