3865. 학회원

1. 위상정렬 설명
2. 문제 링크

1. 문제 해결

---

문제에서 중요하게 생각해야할 부분은 아래와 같다.

제일 처음으로 주어지는 학회에 포함되어 있는 회원의 수를 출력한다.

우선, 문제의 입력값이 정수가 아니기에 전처리 과정을 거쳐야한다. 필자는 아래와 같이 전처리 과정을 거쳤다.

1. Map를 이용하여 학회(key) 에 맞는 회원(val) 들을 담는다.
2. Set을 이용하여 입력으로 주어진 모든 값을 담는다.

✔ 2번 과정을 거치는 이유는 입력으로 주어진 문자열을 넘버링 하기 위해서이다.

---

1-1. 위상정렬로 접근

전처리 과정을 거친 후, 처음에는 위상정렬로 문제를 접근했다.
하지만, 예제로 주어진 값 외에 다른 값들을 넣어보니 틀린 값이 발생하였다.

다른 예제들의 입력값들을 확인해 본 결과, 학회 내에 회원 이름과 학회 속의 학회에 회원 이름이 중복 되는 것을 확인하였다.

---

1-2. 유니온 파인드(Union-Find)로 접근

문제에서 주어진 "제일 처음으로 주어진 학회에 ... " 에 힌트를 얻어 유니온 파인드로 진행하였다.

유니온 파인드의 과정은 아래와 같다.

1. 현재 학회와 회원을 비교한다.
   1-1. 학회의 부모 == 회원의 부모인 경우, 다음으로 넘어간다.
   1-2. 학회와 부모 != 회원의 부모인 경우, 회원이 학회인지 아닌지 판단한다. 회원이 학회가 아닌 경우, 순수 회원 이름이므로 회원 수를 증가시킨다.

회원이 학회인지 아닌지 판단할 수 있는 방법은 전처리 과정에서 만든 Map을 이용하여 판단한다. ex) 회원이 Map의 키 값으로 들어 있는 경우 학회이다

2. 소스 코드

//학회원
import java.util.*;
import java.io.*;

public class Main {
	static List<String> adj;
	static int [] parent; 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = -1;
		while ((n = Integer.parseInt(br.readLine())) != 0) {
			Map<String, Set<String>> map = new HashMap<>();
			Set<String> temp = new LinkedHashSet<>(); // 넘버링을 하기 위한 집합
			for (int i = 0; i < n; i++) {
				String[] split = br.readLine().split(":");
				String key = split[0];
				temp.add(key);
				Set<String> val = makeValue(temp, split[1]);

				map.put(key, val);
			}

			unionFind(temp, map);
			map = null;
			temp = null;
		}

		br.close();
	}

	private static void unionFind(Set<String> total, Map<String, Set<String>> map) {
		adj = new ArrayList<>(total);
		parent = new int[adj.size()];
		
		for(int i =0 ; i < parent.length ; i++)
			parent[i] = i;
		
		Queue<String> q = new LinkedList<>();
		q.add(adj.get(0));

		int ans= 0;
		while(!q.isEmpty()) {
			String cur = q.poll();
			
			for(String val : map.get(cur)) {
				if(union(val,cur)) {
					if(map.containsKey(val)) {
						//학회 인 경우
						q.add(val);
					}else
						ans++;
				}
			}
		}
		
		System.out.println(ans);
	}
	
	private static boolean union(String c1, String c2) {
		int p1 = find(adj.indexOf(c1));
		int p2 = find(adj.indexOf(c2));
		
		if(p1 == p2)
			return false;
		
		if(p1 < p2)
			parent[p2] = p1;
		else
			parent[p1] = p2;
		
		return true;
	}
	
	private static int find(int p1) {
		if(p1 == parent[p1])
			return p1;
		else
			return find(parent[p1]);
	}

	private static Set<String> makeValue(Set<String> temp, String split) {
		split = split.replace(".", "");
		Set<String> ret = new HashSet<>();

		String[] tmp = split.split(",");

		for (int i = 0; i < tmp.length; i++) {
			temp.add(tmp[i]);
			ret.add(tmp[i]);
		}

		return ret;
	}
}