[백준] 20303 할로윈의 양아치

1. 문제

www.acmicpc.net/problem/20303

20303번: 할로윈의 양아치

2. 접근방법

0/1 KnapSack과 거기에 쓰일 집합들을 직접 구해 푸는 문제

 

처음 주어진 관계들에서 서로 연결된 요소들의 캔디양(value)과 사람수(weight)를 구한 뒤

 

0/1 KnapSack과 같이 DP로 문제를 해결하면 된다.

 

서로 연결된 요소를 구하는 방법엔 bfs, dfs, Union find 등이 있을 것 같은데

나는 직관적으로 떠오른 bfs를 사용했다.

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class G3_20303할라윈의양아치 {
	static class group{
		int candy;
		int head;
		public group(int candy, int head) {
			this.candy = candy;
			this.head = head;
		}
		
	}
	static int candies[];
	static ArrayList<group> groups = new ArrayList<group>();
	static ArrayList<Integer> relation[];
	static boolean visit[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); //아이 수
		int M = Integer.parseInt(st.nextToken()); //관계 수
		int K = Integer.parseInt(st.nextToken()); //뺏는 수
		relation = new ArrayList[N];
		visit = new boolean[N];
		for(int i = 0 ; i < N ; i++)
			relation[i] = new ArrayList<Integer>();
		candies = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; i++)
			candies[i] = Integer.parseInt(st.nextToken());
		for(int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			int to = Integer.parseInt(st.nextToken())-1;
			int from = Integer.parseInt(st.nextToken())-1;
			relation[to].add(from);
			relation[from].add(to);
		}
		for(int i = 0 ; i < N ; i++) { //group 만들기
			if(visit[i])
				continue;
			bfs(i);
		}
		int dp[][] = new int[2][K];
		for(int i = 0 ; i < groups.size() ; i++) {
			group now = groups.get(i);
			int head = now.head;
			int candy = now.candy;
			for(int j = 0 ; j < K ; j++) {
				if(j>=head && dp[0][j-head]+candy > dp[0][j])
					dp[1][j] =dp[0][j-head]+candy;
				else
					dp[1][j] = dp[0][j];
			}
			dp[0] = dp[1].clone();
		}
		System.out.println(dp[1][K-1]);
	}
	
	static void bfs(int start) {
		visit[start] = true;
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(start);
		int head = 1,candy = candies[start];
		while(!que.isEmpty()) {
			int now = que.poll();
			for(int i : relation[now]) {
				if(visit[i])
					continue;
				visit[i] = true;
				que.offer(i);
				head++;
				candy += candies[i];
			}
		}
		groups.add(new group(candy,head));
	}

}

4. 마치며

두가지 개념이 섞여서 그렇지

그렇게 어렵진 않게 해결한 문제이다.