[백준 20119 JAVA] 클레어와 물약

 

지난 문제와 같이 위상정렬을 이용하는 문제이다.

 

단, 간단한 위상정렬 구현만으로 풀리지 않는다.

 

 

5번 물약을 만드는 레시피가 1,2 또는 3,4라고 하자

 

단순 위상정렬로 구현한다고 할때 5번 노드로 진입경로는 4개가 된다.

그럼 1,2 또는 3,4 가 둘중 한쌍만 들어왔을때 아직 잔여 진입경로는 2가되므로 답이 되지 않는다.

 

따라서 기존과 약간 다르게 위상정렬을 구현해야 한다.

 

경로를 바로 저장하지 말고, 레시피를 그래프에 저장해 보자

 

5번 물약은 0번재 래시피를 만드는데 쓰인다 이런식으로 말이다.

 

그리고 진입경로는 N번째 래시피로 도달하는 진입경로의 개수를 저장해 준다.

 

추후 L을받고 y를 받으면 Y를 스택 또는 큐에 넣어준다.

 

큐에서 하나씩 Y를 꺼낸다. 그래프의 y번째에는 y번물약이 쓰이는 레시피들이 저장되어있다.

y물약이 쓰이는 레시피의 진입경로를 하나씩 없에주고 y번째물약에 방문표시를 한다.

 

진입경로가 0인 레시피들을 반복해서 위의 작업을 하다보면 답이 나온다.

 

위상정렬을 어떻게 응용하는지 생각해보는 문제였다.

 

 

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

class Main{
    public static void main(String[] args) throws IOException {
        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());

        ArrayList<Integer>[] graph = new ArrayList[N+1];
        int[] target = new int[M];
        int[] inputCount = new int[M];
        Boolean[] visited = new Boolean[N + 1];
        for(int i=0; i<=N;i++){
            visited[i] = false;
            graph[i] = new ArrayList<>();
        }


        for(int i= 0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            inputCount[i] = k;
            for (int j=0; j<k; j++){
                graph[Integer.parseInt(st.nextToken())].add(i);
            }
            target[i] = Integer.parseInt(st.nextToken());
        }
        int L = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0 ; i<L; i++){
            int y = Integer.parseInt(st.nextToken());
            queue.add(y);
            visited[y]= true;
        }
        while (!queue.isEmpty()){
            int temp =queue.poll();
            for(int next : graph[temp]){
                if( --inputCount[next] ==0 && (!visited[target[next]])){
                    visited[target[next]] = true;
                    queue.add(target[next]);
                }
            }
        }
        int count = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i<=N;i++){
            if(visited[i]){
                count++;
                sb.append(i).append(" ");
            }
        }
        System.out.println(count);
        System.out.println(sb);
    }
}