위상 정렬

백준 2252 골드3(자바)
백준 1005 골드3(자바)

위상 정렬 topological sorting

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
시간 복잡도 O(V + E)
항상 유일한 값으로 정렬되지 않음.

위상 정렬 원리

1. 진입 차수: 자기 가신을 가리키는 에지의 개수
   ArrayList<node>[n]로 (자신이 가리키는 인접 리스트)그래프를 표현하고

• 진입 차수 배열 D[n]을 인덱스를 가리키는 에지의 개수로 초기화

2. 진입 차수가 0인 노드를 선택하고 선택한 노드를 위상 정렬 배열에 저장 -> 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺌.
   예) 1번 노드의 진입 차수가 0이면 1을 위상 정렬 배열에 저장하고 1이 가리키는 노드들의 진입 차수를 1씩 뺌.

3. 2 반복

백준 2252

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;

public class Main {

    public static ArrayList<Integer>[] graph; // 인접 리스트
    public static int[][] edgeInCnt; // 진입 차수 저장 + 위상 정렬에 저장된 값인지
    public static Queue<Integer> q; // 위상 정렬 저장
    public static int N, M;

    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());

        graph = new ArrayList[N+1];
        edgeInCnt = new int[N+1][2];
        q = new LinkedList<Integer>();

        // 인접 리스트 초기화
        for(int i=0;i<graph.length;i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int f = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[f].add(b);
            edgeInCnt[b][0]++;
        }

        while(q.size()!=N) {
            int now = 0;
            // 가능하면 앞번호부터 순서대로
            for (int i = 1; i < edgeInCnt.length; i++) {
                if (edgeInCnt[i][0] == 0 && edgeInCnt[i][1] == 0) {
                    now = i;
                    break;
                }
            }
            q.add(now);
            edgeInCnt[now][1] = 1;
            for(int i:graph[now]){
                if(edgeInCnt[i][0]!=0){
                    edgeInCnt[i][0]--;
                }
            }
        }


        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }

    }

}

백준 1005

2252 응용해서 품(dp의 개념을 이용)

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;

public class Main {

    public static ArrayList<Integer>[] graph; // 인접 리스트
    public static int[][] edgeInCnt;
    // 진입 차수 저장 + 위상 정렬에 저장된 값이 아니면 0 맞으면 1 + weight 저장(dp처럼)
    public static Queue<Integer> q; // 위상 정렬 저장
    public static int N, K, W;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int t = 0; t<T;t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            graph = new ArrayList[N + 1];
            edgeInCnt = new int[N + 1][3];
            q = new LinkedList<Integer>();

            // 인접 리스트 초기화
            for (int i = 0; i < graph.length; i++) {
                graph[i] = new ArrayList<>();
            }

            int[] weight = new int[N + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                weight[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int f = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                graph[f].add(b);
                edgeInCnt[b][0]++;
            }
            W = Integer.parseInt(br.readLine());

            while (q.size() != N) {
                int now = 0;
                for (int i = 1; i < edgeInCnt.length; i++) {
                    if (edgeInCnt[i][0] == 0 && edgeInCnt[i][1] == 0) {
                        now = i;
                        break;
                    }
                }
                if (now == W) {
                    break;
                }
                q.add(now);
                edgeInCnt[now][1] = 1;
                for (int i : graph[now]) {
                    edgeInCnt[i][0]--;
                    if (edgeInCnt[i][2] == 0) {
                        edgeInCnt[i][2] = edgeInCnt[now][2] + weight[now];
                    } else if (edgeInCnt[i][2] < edgeInCnt[now][2] + weight[now]) {
                        edgeInCnt[i][2] = edgeInCnt[now][2] + weight[now];
                    }
                }
            }

            System.out.println(edgeInCnt[W][2] + weight[W]);

        }
    }

}