[Java] 백준 20119번: 클레어와 물약 - Topology Sort(위상 정렬)

 

https://www.acmicpc.net/problem/20119

20119번: 클레어와 물약

문제

세상에는 N종류의 물약이 있고 클레어는 M개의 레시피를 알고있다.

레시피는 (x1, x2, ..., xk) → r 형태로 표현할 수 있고 x1번, x2번 ..., xk번 물약을 모두 섞어서 r번 물약을 만들 수 있다는 뜻이다.

현재 클레어에게는 y1번, y2번, ..., yL번 물약만 있다. 만들 수 있는 물약들을 전부 알아내주자.

클레어가 가지고 있는 각 종류의 물약의 양은 무한대라고 가정하자.

입력

첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다.

다음 M개의 줄에는 각각의 줄마다 레시피의 정보 ki, xi1, xi2, ..., xiki, ri (1 ≤ ki < N, 1 ≤ xij, ri ≤ N, xij ≠ ri) 가 주어지며 이는 (xi1, xi2, ..., xiki) → ri 형태의 레시피를 의미한다.

M+2 번째 줄에는 현재 클레어가 가지고 있는 물약 종류의 수 L (1 ≤ L < N) 이 주어진다.

M+3 번째 줄에는 y1, y2, ..., yL (1 ≤ yi ≤ N) 이 주어진다.

모든 ki의 합은 400,000을 넘지 않는다.

출력

첫 번째 줄에 클레어가 만들 수 있는 물약의 개수를 출력한다.

두 번째 줄에는 만들 수 있는 물약의 번호를 오름차순으로 출력한다.

 

---

 

 

문제 설명이 부족한 것 같아서 추가 설명을 붙이면 좋을 것 같다.

• x1, x2, ... xk는 순서가 바뀌어도 상관없다. 모두 가지고 있으면 r번 물약을 만들 수 있다.
• 여러개의 레시피로 같은 물약을 만들 수 있다.

1, 2로도 3을 만들 수 있으며 4, 5로도 3을 만들 수 있을 가능성이 있다.

• 입력값의 k는 뒤에 나오는 x1, x2, ... 의 개수이다. 그리고 마지막 r은 물약의 번호이다.

이 문제는 기존의 위상 정렬에서 조금 더 응용해야 했다.

위상정렬을 모른다면 아래 블로그 참고!

https://h-yeon00.tistory.com/40

[Algorithm] Topology Sort (위상 정렬)

 

기존의 위상 정렬은 각각의 노드에 대한 진입차수를 저장하는 배열을 만들었다면

이 문제에서는 노드의 인덱스에 대한 진입차수를 저장하는 배열을 만들어야 한다.

 

먼저 내가 착각한 부분이다.

 

r을 구하기 위해서는 이전의 x1, x2, ... 가 만족되어야 하므로 선후 관계이다.

따라서 기존의 위상 정렬처럼 list[x1].add(r) 이런식으로 넣어주고, 진입차수를 증가시켜주었다.

//맨 뒤에 있는 r을 먼저 구하기 위해 split 사용
for(int i=0; i<m; i++){
    String[] str = br.readLine().split(" ");

    int k = Integer.parseInt(str[0]);
    int r = Integer.parseInt(str[str.length-1]);

    for(int j=1; j<=k; j++){
        int a = Integer.parseInt(str[j]);
        list[a].add(r);
        indegree[r]++;
    }
}

 

레시피 중 하나가 [2 4 5 3] 이라고 하면

list[4].add(3);

list[5].add(3);

indegree[3] = 2가 되어있을 것이다.

 

여기서 또 다른 레시피인 [3 1 2 6 3] 이 있다면

list[1].add(3);

list[2].add(3);

list[6].add(3);

indegree[3] = 5가 된다.

기존에 있던 indegree[3] = 2에서 +3을 하게 된다.

 

그래서 여기서 topologySort()를 적용해도 indegree[3] == 0 이 될 수가 없어 답을 만족시키지 못한다.

 

그럼 어떻게 해야하는가?!

 

같은 물약에 진입차수가 추가로 증가되지 않도록 해줘야 한다.

레시피마다 각각의 인덱스를 부여하고, 해당 레시피에 대한 물약은 따로 저장해두는 것이다.

for(int i=0; i<m; i++){
    st = new StringTokenizer(br.readLine());

    int k = Integer.parseInt(st.nextToken());

    for(int j=0; j<k; j++){
        int a = Integer.parseInt(st.nextToken());
        list[a].add(i);		//i: 레시피 인덱스
    }

    indegree[i] = k;
    int r = Integer.parseInt(st.nextToken());
    drug[i] = r;	//drug: 실제 물약인 r을 저장할 배열
}

 

중복을 막기 위해 HashSet으로 물약을 저장한다.

클레어가 이미 가지고 있는 물약은 진입 차수가 0이라는 뜻이므로 Queue에 먼저 넣어두고, set에 넣어준다.

HashSet<Integer> set = new HashSet<>();
Queue<Integer> queue = new ArrayDeque<>();

for(int i=0; i<l; i++){
    queue.offer(ingredient[i]);
    set.add(ingredient[i]);
}

 

Queue에서 하나씩 꺼내면서 연결된 인덱스에 대한 진입 차수를 감소시킨다.

감소시켰으니 진입 차수가 0인 값은 Queue에 넣어주면된다. 단, 중복되지 않도록 set에 없는 물약이어야 한다.

그리고 set은 인덱스가 아닌 물약에 대한 정보를 지니고 있으므로 인덱스를 drug[i]를 통해 물약의 값으로 바꿔줘야 한다.

while (!queue.isEmpty()){
    int now = queue.poll();

    for(int i : list[now]){
        indegree[i]--;
        if(indegree[i] == 0 && !set.contains(drug[i])){
            queue.offer(drug[i]);
            set.add(drug[i]);
        }
    }
}

 

마지막으로 오름차순으로 정렬해서 출력해야 하므로 HashSet을 List로 변환한다.

List<Integer> result = new ArrayList<>(set);

Collections.sort(result);

sb.append(result.size()).append("\n");

for(int i : result){
    sb.append(i).append(" ");
}

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n, m, l;
	static int[] indegree, drug;
	static List<Integer>[] list;
	static boolean[] visit;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		indegree = new int[m];
		drug = new int[m];
		list = new List[n+1];
		visit = new boolean[n+1];

		for(int i=1; i<=n; i++){
			list[i] = new ArrayList<>();
		}

		for(int i=0; i<m; i++){
			st = new StringTokenizer(br.readLine());

			int k = Integer.parseInt(st.nextToken());

			for(int j=0; j<k; j++){
				int a = Integer.parseInt(st.nextToken());
				list[a].add(i);
			}

			indegree[i] = k;
			int r = Integer.parseInt(st.nextToken());
			drug[i] = r;
		}

		l = Integer.parseInt(br.readLine());

		int[] ingredient = new int[l];

		st = new StringTokenizer(br.readLine());

		for(int i=0; i<l; i++){
			ingredient[i] = Integer.parseInt(st.nextToken());
		}

		topologySort(ingredient);

		System.out.println(sb);
	}

	public static void topologySort(int[] ingredient){
		HashSet<Integer> set = new HashSet<>();
		Queue<Integer> queue = new ArrayDeque<>();

		for(int i=0; i<l; i++){
			queue.offer(ingredient[i]);
			set.add(ingredient[i]);
		}

		while (!queue.isEmpty()){
			int now = queue.poll();

			for(int i : list[now]){
				indegree[i]--;
				if(indegree[i] == 0 && !set.contains(drug[i])){
					queue.offer(drug[i]);
					set.add(drug[i]);
				}
			}
		}

		List<Integer> result = new ArrayList<>(set);

		Collections.sort(result);

		sb.append(result.size()).append("\n");

		for(int i : result){
			sb.append(i).append(" ");
		}
	}
}