[Baekjoon] 3018_캠프파이어

Silver III

문제(출처: https://www.acmicpc.net/problem/3018)

---

< 캠프파이어 >

 

문제 풀이 

 

각 사람이 아는 노래를 ArrayList <HashSet>에 저장한다. 만약 1 = [2], 2 = [3], 3 = [1]인 경우 2번과 3번이 캠프파이어에 참여했다면 서로 아는 노래를 공유한다. 서로 공유하면 1 = [2], 2 = [1,3], 3 = [1,3] 이 된다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class _3018_ { // 캠프파이어

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		int e = Integer.parseInt(bf.readLine());

		ArrayList<HashSet<Integer>> list = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			list.add(new HashSet<>());
		}

		int idx = 0;
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(bf.readLine());

			int k = Integer.parseInt(st.nextToken());
			int num[] = new int[k];
			boolean flag = false;
			for (int j = 0; j < k; j++) {
				num[j] = Integer.parseInt(st.nextToken());
				if (num[j] == 1) {
					flag = true;
				}
			}
			if (flag) {
				idx += 1;
				for (int j = 0; j < k; j++) {
					list.get(num[j]).add(idx);
				}
			} else {
				for (int j = 0; j < k; j++) {
					for (int l = 0; l < k; l++) {
						if (j == l) {
							continue;
						}
						for (int m : list.get(num[j])) {
							list.get(num[l]).add(m);
						}
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			if (list.get(i).size() == idx) {
				bw.write(i + "\n");
			}
		}
		bw.flush();
	}
}

변수)
n : 참가한 사람 수
e : 조건 수
list : ArrayList <HashSet> 각 사람이 아는 노래 번호
idx : 노래 번호
k : 그날 캠프파이어에 참가한 사람의 수
num : 참가한 사람의 번호를 저장한 배열
flag : 1번 참가여부

 

참가한 사람의 수 n과 조건 개수 e를 입력받는다. e만큼 캠프파이어에 참가한 사람의 수 k와 참가한 사람의 번호를 입력받는다. 참가한 사람의 번호를 입력받아 num에 저장하면서 1번이 참가했는지 확인한다. 1번이 참가했다면 새로운 노래를 만들어야 하므로 참가한 사람들의 HashSet에 idx를 저장한다. 1번이 참가하지 않았다면 각자 아는 노래를 서로 공유해야 하므로 각자 HashSet을 순환하며 다른 사람들의 HashSet에 값을 저장한다. 최종 ArrayList를 순환하며 각 사람들의 HashSet의 size가 idx와 일치한다면 모든 노래를 아는 사람이므로 출력한다.

---

---