[Algorithm] 위상 정렬 (boj 2252, boj 1005)

위상 정렬은 이런 느낌

A가 B 앞에 나와야한다 같은 조건이 나오는 문제

 

풀이
1. adj, indegree 배열 정의
2. indegree가 0인걸 저장할 큐 정의
3. 큐 초기화 (indegree가 0인걸 넣어줌)
4. 큐에서 pop 된 원소의 adj indegree를 하나씩 빼준다. 이때 indegree가 0이 된다면 q에 add

boj 2252

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        ArrayList<Integer> answer = new ArrayList<>();

        // indegree
        int[] indegree = new int[N+1];

        // adj 초기화
        ArrayList<Integer>[] adjs = new ArrayList[N+1];
        for(int i = 1; i <= N; i++) {
            adjs[i] = new ArrayList<>();
        }

        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());

            // n1 -> n2
            // adj[n1] : n2 추가
            // n2 indegree += 1
            ArrayList<Integer> temp = adjs[n1];
            temp.add(n2);
            adjs[n1] = temp;

            indegree[n2] += 1;
        }

        // indegree 가 0인 원소를 저장할 큐
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= N; i++) {
            if(indegree[i] == 0) q.offer(i);
        }

        // 큐에서 pop 시키면서 하나씩 degree를 감소시킬 것
        while(!q.isEmpty()) {
            int poll = q.poll();
            answer.add(poll);

            for(int adj : adjs[poll]) {
                indegree[adj]--;
                if(indegree[adj] == 0) q.add(adj);
            }
        }

        int[] ints = answer.stream().mapToInt(i -> i).toArray();
        for(int i = 0; i < ints.length; i++) {
            bw.write(ints[i] + " ");
        }
        bw.flush();
    }
}

boj 1005

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int[] result = new int[N+1];

            ArrayList<Integer>[] adjs = new ArrayList[N+1];
            for(int i = 1; i <= N; i++) {
                adjs[i] = new ArrayList<>();
            }

            int[] indegree = new int[N+1];
            int[] cost = new int[N+1];

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

            while(K-- > 0) {
                st = new StringTokenizer(br.readLine());
                int n1 = Integer.parseInt(st.nextToken());
                int n2 = Integer.parseInt(st.nextToken());

                ArrayList<Integer> temp = adjs[n1];
                temp.add(n2);
                adjs[n1] = temp;
                indegree[n2] += 1;
            }

            st = new StringTokenizer(br.readLine());
            int target = Integer.parseInt(st.nextToken());

            Queue<Integer> q = new LinkedList<>();
            for(int i = 1; i <= N; i++) {
                if(indegree[i] == 0) {
                    q.add(i);
                    result[i] = cost[i];
                }
            }

            boolean flag = false;
            while(!q.isEmpty() && !flag) {
                int poll = q.poll();

                for(int e: adjs[poll]) {
                    result[e] = Math.max(result[e], result[poll] + cost[e]);
                    indegree[e]--;
                    if(indegree[e] == 0) {
                        q.add(e);
                    }
                }
            }

            bw.write(result[target] + "\n");

        }
        bw.flush();
    }
}

이전 문제와 달리 최종 값을 어떻게 내야될지에 대해서 고민을 많이 했던 문제!

이전 문제는 종료 조건이 없지만 여기에서는 특정 건물이 종료 조건이 된다.

 

종료되면 모든 프로세스를 종료시키는 것 보다는 직접 걸리는 시간 테이블을 갱신해주는게 좋은 방법이다. 

(지금 건물 짓는데 걸리는 시간 + 이전 건물 짓는데 걸린 시간)

 

플로이드 워샬과 비슷한 느낌

https://www.acmicpc.net/problem/2458
플루이드 워샬 - O(N^3) 안에 될 수 있으면 플루이드 워샬
위상 정렬 - 정렬된 배열을 놓을거긴 하지만 답이 여러 개 가능 

 

2458번: 키 순서