[BOJ] 백준 2213번 트리의 독립집합 (Java)

#2213 트리의 독립집합

난이도 : 골드 1

유형 : 트리 순회/ DP

2213번: 트리의 독립집합

▸ 문제

그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 에지가 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다.

문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다.

▸ 입력

첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 에지 리스트가 주어지는데, 한 줄에 하나의 에지를 나타낸다. 에지는 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 콤마가 없고 대신 빈칸이 하나 혹은 그 이상 있다. 가중치들의 값은 10,000을 넘지 않는 자연수이다.

▸ 출력

첫째 줄에 최대 독립집합의 크기를 출력한다. 둘째 줄에는 최대 독립집합에 속하는 정점을 오름차순으로 출력한다. 최대 독립 집합이 하나 이상일 경우에는 하나만 출력하면 된다.

 

 

문제 풀이 

트리 구조로 되어있는 그래프를 탐색하여 최댓값을 구하는 문제이다.  이는 DP와 DFS방식을 사용하여  풀이를 하면 된다.

* 이러한 유형은 카카오 기출에서 한 번 나온적이 있으니 참고

📚 조건

 ∙ 트리의 정점의 수 n  (1<= n <= 10,000)

 ∙ 정점 i의 가중치 w ( 1 <= i <= n, 1 <= w <= 10,000)

 

+ 이 그래프는 트리의 구조이기 때문에 간선의 수는 n-1이다.

 

풀이 과정은 일단 트리 순회를 하여 독립관계의 최댓값을 찾아낸다. 그럼 루트노드가 참석했냐 안했냐에 따라 노드를 다시 역추적하여 독립 집합에 참석한 노드를 조회해주면 된다.

 

트리 순회 로직

잘못된 접근 방법

1) 트리 구조이기 때문에 1을 루트노드로 지정하여 DFS탐색으로 모든 트리 노드를 조회한다.

→ 위험한 생각이었다. 1을 루트노드라고 문제에서 조건이 주어지지 않은 이상 이와 같이 단방향 탐색으로 풀이하면 안된다.

다른 숫자가 1이랑 같은 Layer에 존재하게 되면 탐색이 중지된다. 그래서 양방향 탐색을 해준 다음 재방문 방지를 위해 방문여부를 체크해줘야 한다.

 

반례 그래프는 다음과 같다.

 

1을 루트노드라 생각하고 단방향 탐색하면 안되는 이유

ex) 7
      1000 3000 4000 1000 2000 2000 7000
      1 4
      1 6
      4 5
      2 6
      2 3
      3 7
      → 답 13000이 나와야 한다.

      → 오답 : 4000 단방향 탐색으로하면 4000나옴 

 

올바른 접근 방법

1) 1번을 시작 노드로 설정하고 양방향 탐색을 통해 모든 노드를 조회한다. (DFS 깊이우선)

2) 각 노드를 조회하면서 참석할 경우(1), 참석하지 않을 경우(0)의 가중치를 dp배열에 저장한다.

 

부모와 자식간의 관계에서 독립 관계를 형성할 경우의 수는 총 3가지이다.

 1. 부모 x - 자식 x

 2. 부모 x - 자식 o

 3. 부모 o - 자식 x 

* (부모 o - 자식 o)이 되면 독립관계아니므로 제외한다.

 

이는 깊이 우선 탐색으로 Stack방식으로 탐색이 되기 때문에 자식의 경우를 고려하여 조건을 설정해주면 된다. 

 

(자식 x > 자식 o)인 경우는 1번과 3번에 해당하고,

(자식 o > 자식 x)인 경우는 2번과 3번에 해당한다.

 

3번은 공통이므로 조건을 따로 설정하지 않고 1번과 2번만 조건을 달아주면 된다.

 

i) 부모가 참석하지 않는 경우

     a) 자식 x > 자식 o 인 경우, (pos는 parent라고 생각하면 됨)

         memo[pos][0] = memo[child][0];

     b) 자식 o > 자식 x 인 경우, 

        memo[pos][0] = memo[child][1];

 

ii) 부모가 참석하는 경우

     a) 자식 x 

         memo[pos][1] = memo[child][0];

 

이를 코드로 나타내면 다음과 같다

static void traversal(int pos) {

	int child_num = node_list[pos].size();
	
	memo[pos][0] = 0; // 참석 x 
	memo[pos][1] = weight[pos]; // 참석 o
	
	if(child_num ==0) return;
	
	check[pos] = true;
	for(int child : node_list[pos]) {
		if(!check[child]) {
			traversal(child);
			
			// 자식 x  > 자식 o
			if(memo[child][0] > memo[child][1]) {
				memo[pos][0] += memo[child][0]; // 부모 x 자식 x 
				
			}else { //  자식 x  < 자식 o
				memo[pos][0] += memo[child][1]; // 부모 x 자식 o
			}
			memo[pos][1] += memo[child][0]; // (공통) 부모 o 자식 x
		}
	}
	check[pos] = false;
	
}

 

위의 과정으로 트리 순회를 하면 탐색의 최종 결과는 다음과 같다. 

 

☛ 최대 독립 집합의 크기는 1번 루트노드가 참석할 경우로 140임을 알 수 있다,

 

독립 집합 추적 로직

이제는 가중치 140일 때, 누가 참석했는지 역으로 조회하면 되는데 위의 그림을 참고하면 쉽게 구할 수 있다. 트리를 순회했을 때의 과정을 생각해보면 자식 노드 가중치가 높은 경우만 값을 저장해줬기 때문에 단순히 생각하면 당연히 역으로 조회할 때는 memo[child][0], memo[child][1] 두 값 중에서 더 높은 값을 찾아 추적하면 된다.

 

시작 케이스는 두가지로, 1번 시작 노드가 참석했을 경우와 1번 시작 노드가 참석하지 않았을 경우로 설정하고 시작 노드부터 재귀 탐색을 진행한다.

 

자식 x > 자식 o ( memo[child][0] > memo[child][1]  ) 인 경우, 

  ☛ 자식은 참여하지 않았을 것이므로 attend = 0으로 설정하여 재귀 호출을 한다.

자식 o > 자식 x인 경우, 

  ☛ 자식이 참여했을 것이므로 attend =1으로 설정하여 List에 추가해준다.

static void trace(int pos, int attend) {
	check[pos] = true;
	if(attend==1) {
		res.add(pos);
		for(int i=0; i<node_list[pos].size(); i++) {
			int next = node_list[pos].get(i);
			if(!check[next]) {
				trace(next, 0);
			}
		}
	}
	else {
		for(int i=0; i<node_list[pos].size(); i++) {
			int next = node_list[pos].get(i);
			if(!check[next]) {
				if(memo[next][1] > memo[next][0]) {
					trace(next, 1);
				}else {
					trace(next, 0);
				}
			}
		}
	}
	check[pos] = false;
	
}

 

풀이 코드 

트리의 구조이기 때문에 일정한 기준을 삼아서 리스트 배열에 값을 잘 저장해줘야 한다. 이 풀이의 경우는 1번 노드를 루트로 설정하기 위해서 작은 값이 부모로 오게 값을 저장했다.

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

public class Main {

	static List<Integer>[] node_list;
	static int[] weight;
	static int[][] memo;
	static boolean[] check;
	static List<Integer> res;	

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		weight = new int[n+1];
		node_list = new ArrayList[n+1];
		memo = new int[n+1][2];
		check = new boolean[n+1];
		res = new ArrayList<>();
		for(int i=0; i<n+1; i++) {
			node_list[i] = new ArrayList<>();
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=1; i<n+1; 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());
		
			node_list[b].add(a);
			node_list[a].add(b);
		}
		
		traversal(1);
		
		if(memo[1][1]> memo[1][0] ) {
			System.out.println(memo[1][1]);
			trace(1,1);
		}else {
			System.out.println(memo[1][0]);
			trace(1,0);
		}
		
		Collections.sort(res);
		for(int num : res ) {
			System.out.print(num+" ");
		}
	}
	
	static void traversal(int pos) {

		int child_num = node_list[pos].size();
		
		memo[pos][0] = 0; // 참석 x 
		memo[pos][1] = weight[pos]; // 참석 o
		
		if(child_num ==0) return;
		
		check[pos] = true;
		
		for(int child : node_list[pos]) {
			if(!check[child]) {
				traversal(child);
				
				// 자식 x  > 자식 o
				if(memo[child][0] > memo[child][1]) {
					memo[pos][0] += memo[child][0]; // 부모 x 자식 x 
					
				}else { //  자식 x  < 자식 o
					memo[pos][0] += memo[child][1]; // 부모 x 자식 o
				}
				
				memo[pos][1] += memo[child][0]; // (공통) 부모 o 자식 x
			}
		}
		check[pos] = false;
	}
	
	static void trace(int pos, int attend) {
		check[pos] = true;
		if(attend==1) {
			res.add(pos);
			for(int i=0; i<node_list[pos].size(); i++) {
				int next = node_list[pos].get(i);
				if(!check[next]) {
					trace(next, 0);
				}
			}
		}
		else {
			for(int i=0; i<node_list[pos].size(); i++) {
				int next = node_list[pos].get(i);
				if(!check[next]) {
					if(memo[next][1] > memo[next][0]) {
						trace(next, 1);
					}else {
						trace(next, 0);
					}
				}
			}
		}
		check[pos] = false;
		
	}
}

 

❍ 비슷한 유형 문제 추천

1949번: 우수 마을

 

+ 트리 순회 카카오 기출 문제

 

❍ 문제 

코딩테스트 연습 - 매출 하락 최소화

 

 

❍ 문제 풀이보기 

[프로그래머스] 2021카카오/ 매출 하락 최소화 (Java) - DOT CODING