Baekjoon_20303_할로윈의 양아치

문제 설명

• 한 아이의 사탕을 뺏으면 친구 것도 다 빼앗음
• K명 이상의 아이들이 울면 더 이상 뺏지 못함

=> K명 미만의 아이들 무리 부분집합 중 얻을 수 있는 최대 사탕 개수 출력하기

 

문제 풀이

이 문제는 0/1 Knapsack을 활용하는 문제이다.

 

0/1 Knapsack을 사용하기 위해서 인접리스트로 주어지는 아이들간의 관계를 이용한 아이들 무리를 만들어야 한다.

 

주어지는 인접리스트를 양방향으로 저장한 후 DFS를 이용하여 각각의 무리를 만들었다.

 

그 무리의 사람 수와 사탕 수를 저장하는 Group이라는 객체를 만들어 ArrayList에 저장했다.

 

그리고 Group을 전부 돌면서 1차원 배열로 dp(코드의 backpack)을 만들어 한계 사람 수(K) -1 부터 그 Group의 사람 수 까지 0/1Knapsack방식으로 수행하였고 최종적으로 배열의 가장 마지막인 K-1번째를 출력하여 답을 도출했다.

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

public class _20303_할로윈의양아치 {
	static class Group {
		int people;
		int candies;

		Group(int people, int candies) {
			this.people = people;
			this.candies = candies;
		}
	}

	static int N, M, K, candy[];
    	static int people, candies;
	static ArrayList<Group> groups = new ArrayList<>();
	static ArrayList<Integer> friends[];
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		candy = new int[N];
		friends = new ArrayList[N];
		visited = new boolean[N];
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < N; ++i) {
			candy[i] = Integer.parseInt(st.nextToken());
			friends[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; ++i) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			friends[a].add(b);
			friends[b].add(a);
		}

		makeGroup(); // 그룹만들기
		
		int[] backpack = new int[K];		//0/1Knapsack
		for(int i = 0; i< groups.size();++i) {
			Group g = groups.get(i);
			for(int j = K-1; j>= g.people;--j) {
				backpack[j] = Math.max(g.candies + backpack[j-g.people], backpack[j]);
			}
		}
		System.out.println(backpack[K-1]);
	}

	
	static void makeGroup() {	//그룹만들기
		for (int i = 0; i < N; ++i) {
			if (visited[i]) // 이미 그룹에 속한 아이라면
				continue;
			people = 1;
			candies = candy[i];
			visited[i] = true;
			findFriends(i);
			groups.add(new Group(people, candies));
		}
	}

	static void findFriends(int idx) {	//dfs
		Iterator<Integer> iter = friends[idx].iterator();
		while (iter.hasNext()) {
			int num = iter.next();
			if (visited[num])
				continue;
			++people;
			candies += candy[num];
			visited[num] = true;
			findFriends(num);
		}
	}
}