위상정렬

접근

위상정렬은 백준의 1005번 ACM Craft 문제를 풀며 배웠다.

백준 1005번 문제가 궁금하시다면 여기를 클릭하세요.

위상 정렬이란 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

위와 같은 그래프가 있다고 할 때
순서는

• "아침에 눈뜨기-> 운동하기->창문열기->아침먹기->세수하기->출근하기"
• 혹은 "아침에 눈뜨기->창문열기->운동하기->아침먹기->세수하기->출근하기"가 될 것이다.

위상정렬의 경우 여러가지의 경우의 수가 가능하지만 먼저 수행해야하는 순서가 결정되는 부분이 존재한다.

위의 경우 세수하기는 운동하기와 아침을 먹은 다음에야 진행할 수 있다.
출근하기는 세수하기와 아침을 먹은 다음에야 진행할 수 수 있다.

그러면 저 그래프의 처음은 어디일까?
바로 아침에 눈뜨기이다.
직관적으로 보인다.
아침에 눈뜨기 전에 아무런 노드가 존재하지 않기 때문이다.

따라서 위상정렬이 성립하려면 위와 같이 적어도 하나는 아무런 조건이 존재하지 않은 노드가 하나는 있어야 한다. 즉 사이클이 발생하지 않는 방향 그래프여야 한다. 이를 DAG(Directed Acyclic Graph)라고 한다.

과정

이를 코드에서 어떻게 나타내야 할까라는 물음이 남아있다.

일단 위상정렬은 순서가 존재한다고 했다.
따라서 가장 먼저 할 일은 가장 처음을 발견하는 것이다.

👆 앞서 말했듯이 그래프의 처음은 나 이전에 아무런 조건 노드가 존재하지 않은 노드이다. 따라서 나를 향하는 화살표가 0인 노드부터 Queue(혹은 Stack)에 넣도록 하자.
넣은 다음에 나와 연결노드로 이동하면서 Queue에 있는 노드를 poll한다.

👆 그 다음에도 위 조건과 마찬가지로 나를 향하는 조건 노드가 존재하지 않으면 Queue(혹은 Stack)에 넣도록하자.

👆 여기서 약간 헷갈릴 수 있지만 세수하기는 세수하기 이전에 자신을 향하는 조건 노드가 남아 있어서 Queue에 넣지 못한다.

👆 과정을 반복하여 위와 같은 결과가 나왔다.

자바 코드

자바 코드를 위에 언급된 문제에 대한 풀이로 대신한다.

import java.io.*;
import java.util.*;

public class Main{

    static ArrayList<ArrayList<Integer>> list;

    public static void main(String[] args)throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        while(T-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken()); // 2~ 1000 건물 수
            int K = Integer.parseInt(st.nextToken());// 1~100,000 규칙 수

            list = new ArrayList<>();

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

            // 비용받기
            int[] cost = new int[N + 1];
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= N; i++) {
                cost[i] = Integer.parseInt(st.nextToken());//0부터 100,000
            }

            int[] rule = new int[N+1];
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int v1 = Integer.parseInt(st.nextToken());
                int v2 = Integer.parseInt(st.nextToken());

                rule[v2]++;

                list.get(v1).add(v2);
            }

            //주인공이 지어야 하는 건물 번호
            int target = Integer.parseInt(br.readLine());

            int answer = solution( target, cost, N,rule);

            bw.write(Integer.toString(answer)+"\n");




        }

        bw.flush();
        bw.close();
        br.close();




    }
    static int solution(int target, int[] cost, int N, int[] rule){
       Queue<Integer> Q = new LinkedList<>();
       int[] result = new int[N+1];

       for(int i=1;i<=N;i++){
           result[i]=cost[i];
           if(rule[i]==0){
               Q.offer(i);
           }
       }

       while(!Q.isEmpty()){
               int q = Q.poll();

               for(int j=0;j<list.get(q).size();j++){
                   int v = list.get(q).get(j);

                   result[v]=Math.max(result[v],cost[v]+result[q]);
                   rule[v]--;
                   if(rule[v]==0){
                       Q.offer(v);
                   }

               }
           }

         return result[target];
    }



}