[코드트리] 7 - Topological Sort, DAG DP

DAG DP 대표 유형 정리

1. 위상 정렬

2. 큐에서 cur을 꺼냈다는 것은 dp[cur] 가 확정되었다는 것

3. cur의 모든 간선을 따라 dp[next]를 갱신함.

 

시작 정점이 정해져있는 문제들은 INF (도달 불가능함을 나타내는 초기값)이 필요하다.

그러나 모든 정점의 값을 계산하는 문제들은 필요없다. 

-> 그냥 다 해놓고 풀자.

 

최장 거리

위상 정렬을 하면서 n을 처리할 때 정방향으로 dp1를 갱신

dp1[i] = 1->i 방향의 최대 거리

역그래프를 활용하고 정방향 위상 순서를 뒤집어서 dp2를 갱신

dp2[i] = i->DEST 방향의 최대 거리

-> dp1[next] = Math.max(dp1[next], dp1[cur] + nextW) 로 갱신

 

최대 정점 경로일 때,

dp1[next] = dp1[cur] + 1 && dp1[next] + dp2[next] - 1 == dp1[DEST] 를 만족하는 next가

최장 거리 경로에 포함된 정점임을 활용함.

 

최대 간선 가중치 경로일 때,

dp1[next] = dp1[cur] + nextW && dp1[cur] + dp2[next] + nextW == dp1[DEST] 

-> 1번 조건은 필요없는게 dp2[next] >= 0 또는 DEST까지의 최적 경로 값이라 

2번 조건을 만족하면 1번 조건은 자동으로 충족됨.

 

X에 도달하는 총 경로 가짓수

위상 정렬을 하면서 n을 처리할 때 dp[next] += dp[cur]

 

필요 부품 총 갯수 (장난감 문제)

위상 정렬을 하면서 n을 처리할 때 

dp[ i ][ j ] = i 번 부품을 만들기 위해 기본 부품 j의 필요 갯수 라고 정의할 때, (크기는 N+1 * N+1)

dp[i][i] = 1로 처음 큐에 들어갈 때 초기화하고

-> for(int i =1; i<=N; i++)

      dp[next][i] += dp[cur][i] * nextW 로  갱신

-> next 하나를 만들기 위해 cur 가 nextW개 만큼 필요하므로

cur를 구성하는 기본 부품의 nextW배 만큼 증가함.

 

동시에 만들 수 있을 때 최소 완성 시간

위상 정렬을 하면서 n을 처리할 때 동시에 건설하거나 제작할 수 있다는 것은 

같은 레벨 위상 순서상 가장 오래 걸리는 시간만 알면 나머지는 동시제작이므로 그 시간 안에 만들어짐

dp[i] = i번 부품을 만들기 위한 최소 시간 이라 정의하면,

초기화는 dp[i] = 0

dp[next] = Math.max(dp[next], dp[cur] + nextW)

---

문제 - 노드 맞추기

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-nodes-guessing/description

노드 맞추기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static String rs() throws IOException{
        sst.nextToken();
        return sst.sval;
    }

    static int N, M;
    static ArrayList<Integer>[] g;
    static ArrayList<Integer>[] child;
    static String[] node;
    static int[] indeg;
    static ArrayList<String> s = new ArrayList<>();

    public static void main(String[] args) throws Exception{
        N = read();
        node = new String[N];
        for(int i = 0; i < N; i++){
            node[i] = rs();
        }

        Arrays.sort(node);
        HashMap<String, Integer> stoi = new HashMap<>();

        for(int i = 0; i < N; i++){
            stoi.put(node[i], i);
        }

        indeg = new int[N];
        g = new ArrayList[N];
        child = new ArrayList[N];

        for(int i = 0; i < N; i++){
            g[i] = new ArrayList<>();
            child[i] = new ArrayList<>();
        }

        M = read();

        while(M-- > 0){
            String a = rs();
            String b = rs();

            int ai = stoi.get(a);
            int bi = stoi.get(b);

            indeg[ai]++;
            g[bi].add(ai);
        }

        PriorityQueue<Integer> q = new PriorityQueue<>();

        for(int i = 0; i < N; i++){
            if(indeg[i] == 0){
                q.add(i);
                s.add(node[i]);
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(s.size()).append("\n");
        for(String str : s){
            sb.append(str).append(" ");
        }
        sb.append("\n");

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

            for(int n : g[ci]){
                if(--indeg[n] == 0){
                    child[ci].add(n);
                    q.add(n);
                }
            }
        }

        for(int i = 0; i < N; i++){
            child[i].sort(Comparator.comparingInt(a -> a));

            sb.append(node[i]).append(" ");
            sb.append(child[i].size());
            for(int c : child[i]){
                sb.append(" ").append(node[c]);
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

입력으로 원래 정점들과 부모 및 조상이 각각 나열되어 있을 때 원래의 트리를 복원하는 문제임.

입력이 자손, 조상 으로 들어와서 처음에 indegree를 잘못 세는 문제가 있었다.. 입력 조건을 잘 볼것.

 

indegree == 0 이 시작점이 되기 때문에 이게 복원된 트리의 갯수가 되고, 다음 노드의 indegree가 0이 되는 순간의 cur 정점이 n노드의 직계 부모 정점이 되므로 이때 복원용 트리 그래프에 기록한다.

---

문제 - 조립 2 (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-assembly-2/description

조립 2 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static ArrayList<Integer>[] g;
    static int[] indeg;
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i=1; i<=N; i++){
            g[i] = new ArrayList<>();
        }

        // 같은 조립법 여러번 들어와서 중복없이 합집합으로 만들어야 함
        // need[a] = a를 만들기 위한 부품 리스트
        Set<Integer>[] need = new HashSet[N+1];
        for(int i = 1; i<=N; i++){
            need[i] = new HashSet<>();
        }

        while(M-->0){
            int a = read();
            int K = read();

            while(K-->0){
                int b = read();
                need[a].add(b);
            }
        }
        int K = read();
        ArrayList<Integer> li = new ArrayList<>();
        while(K-->0)
            li.add(read());

        for(int i = 1; i<=N; i++){
            for(int b : need[i]){
                g[b].add(i);
                indeg[i]++;
            }
        }


        // 위상정렬 시작
        // 시작점으로는 가지고 있는 조각 전부 다 넣기
        boolean[] have = new boolean[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        for(int n : li){
            have[n] = true;
            q.add(n);
        }

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

            for(int n : g[ci]){
                // have로 중복방지하고 중복 기여 막음
                if(--indeg[n] == 0 && !have[n]){
                    have[n] = true;
                    li.add(n);
                    q.add(n);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(li.size()).append("\n");
        Collections.sort(li);
        for(int n : li){
            sb.append(n).append(" ");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

입력으로 1번부터 N번까지의 조각이 주어지고 조립법 M개가 주어짐. 그리고 이미 갖고있는 부품도 주어짐.

조립법은 만들수 있는 부품 과 그것을 만드는데 필요한 부품 수 K와 K개의 부품 정점이 나열됨. 

여기서 중복된 조립법이 들어올 수 있고 조립법을 모두 만족해야 부품이 만들어짐.

-> 5 2 1 4와 5 2 1 3 이라는 입력이 들어오면 5번을 만들기 위해서 1, 3, 4 의 부품이 필요하다는 것이 된다. 
-> 따라서 need라는 HashSet 배열을 마련해서 합집합을 중복없이 관리해서 입력받고 

나중에 need를 순회하면서 그래프와 indegree 배열을 계산한다.

 

위상정렬 파트에서는 처음 시작 큐에 이미 갖고 있는 부품을 넣게 된다. 

여기서 이미 갖고 있는 부품이 나중에 위상정렬이 진행되면서 또 들어가게 되면

중복 기여를 하여 만들어질 수 없는 부품이 만들어질 수 있다.

-> 처음 큐에 넣을 때와 나중에 조건이 만족되어 큐에 넣을때 visited 체크를 한다.

 

이미 갖고 있는 부품을 저장하기 위해서 썻던 List에 위상 정렬을 진행할 때 큐에 넣을때 같이 저장한다.

-> visited로 중복이 해결되므로 굳이 Set으로 따로 빼서 관리할 이유가 없다. 

-> Kahn에서는 사실 --indeg == 0일때 딱 한번만 들어가서 중복은 안 되는데

여기서 visited는 방문 상태 + 현재 가지고 있는 조각 (새로 만든 조각 포함) 의 인벤토리 역할을 겸함.

-> 이미 가진 부품을 또 만들면 안된다는 것이 중요하다.

li로 적절히 출력해주면 끝

---

문제 - 사이클 없애기 (다시 풀기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-remove-cycle/description

사이클 없애기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M1,M2;
    static int[] indeg;
    static ArrayList<Integer>[] g;


    public static void main(String[] args) throws IOException{
        N = read();
        M1 = read();
        M2 = read();
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i =1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        while(M1-->0){
            int a = read();
            int b = read();
            g[a].add(b);
            indeg[b]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        boolean[] v = new boolean[N+1];
        for(int i = 1; i<=N; i++){
            if(indeg[i] == 0)
                q.add(i);
        }

        int cnt = 0;
        while(!q.isEmpty()){
            int ci = q.poll();
            if(v[ci])
                continue;
            v[ci] = true;

            for(int n : g[ci]){
                if(--indeg[n] == 0 && !v[n]){
                    q.add(n);
                }
            }
        }

        for(int i =1 ;i<=N; i++){
            if(!v[i]){
                System.out.print("No");
                return;
            }
        }
        System.out.print("Yes");
    }
}

사고의 흐름 및 풀이

단방향 간선 m1개와 양방향 간선 m2개가 주어질 때, 양방향 간선을 적절히 배치해서 사이클이 생기지 않게 할 수 있는가?

 

단방향 간선이 있는 그래프는 항상 위상정렬이 가능하다.

따라서, 위상 순서가 앞인 정점을 우선해서 모든 양방향 간선을 정하게 되면 

모든 간선이 위상 순서를 증가시키는 방향이 되므로 사이클이 생길 수가 없는 구조가 된다. 

-> 만약 m1개의 단방향 그래프에서 사이클이 발생한다면 양방향 그래프에서 어떻게 간선을 정하던 사이클이 발생한다. 

단방향 그래프의 간선은 문제 조건상 수정할 수 없기 때문이다.

-> m1개의 간선 정보로 그래프를 구성하고 위상정렬 후 사이클 여부를 판단하면 된다.

---

문제 - 친구의 키 (파라메트릭 서치)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-height-of-friends-4/description

친구의 키 4 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] indeg;
    static ArrayList<Integer>[] g;
    static int[][] clue;

    static boolean can(int x){
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i=1 ;i<=N; i++){
            g[i] = new ArrayList<>();
        }

        for(int i = 1; i<=x; i++){
            int a = clue[i][0];
            int b = clue[i][1];
            g[a].add(b);
            indeg[b]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0;
        for(int i =1 ; i<=N; i++)
            if(indeg[i] == 0)
                q.add(i);
        
        while(!q.isEmpty()){
            int ci = q.poll();
            cnt++;

            for(int n : g[ci]){
                if(--indeg[n] == 0)
                    q.add(n);
            } 
        }

        return cnt == N;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        clue = new int[M+1][2];

        for(int i=1; i<=M; i++){
            int a = read();
            int b = read();
            // a가 b보다 크다
            // -> a가 우선순위가 높다 
            clue[i] = new int[]{a,b};
        }

        // 중요! 단서가 M개라서 1~M으로 해야함
        int l = 1;
        int r = M;
        int ans = -1;
        while(l<=r){
            int mid = (l+r)/2;
            // mid 번째 단서까지 봤을때 모순이 발생하지 않는가?
            // -> 모순이 발생하지 않았으면 더 뒤에서 봐야함
            if(can(mid)){
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        System.out.print(ans == M ? "Consistent" : (ans+1));
    }
}

사고의 흐름 및 풀이

큰 키부터 내림차순으로 우선하여 키가 큰 사람의 정보가 주어졌을 때 모순이 발생하는 첫 단서의 번호를 출력하거나 만약 모순이 발생하지 않는다면 Consistent 문자열 출력하는 문제임.

어떤 간선의 정보 이후에 모순이 발생한다는건 사이클이 발생한다는 것이고 

그 이후부터는 간선을 뭘 추가하든 간에 간선 제거를 하지 않는 이상 사이클을 제거할 수 없음. 

-> 단조성을 띄므로 이분탐색을 활용할 수 있음.

문제에서는 간선 제거 옵션이 없으니 최초의 사이클 발생 지점을 찾으면 됨. 

 

문제 제한이 N과 M 둘다 10만이므로 1부터 X까지 봤을 때 모순이 발생하지 않는가?의 가장 작은 지점을 찾고 +1하면 답임

이분탐색으로 ans가 M이라면 모든 단서를 봤을 때 모순이 발생하지 않았으므로 consistent한 거임.

-> can 함수 호출마다 1에서 X 인덱스 까지의 간선으로 그래프를 매번 새로 생성하고 위상정렬로 사이클 여부를 판단

---

문제 - 새로운 알파벳 (외계어 사전, DAG의 유일성 판독)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-new-alphabet/description

새로운 알파벳 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static String rs() throws IOException{
        sst.nextToken();
        return sst.sval;
    }

    static int M,N;
    static String[] cl;
    static int[] indeg;
    static ArrayList<Integer>[] g;

    public static void main(String[] args) throws IOException{
        M = read();
        cl = new String[M];

        Set<Integer> ss = new HashSet<>();
        for(int i = 0; i<M; i++){
            String s = rs();
            char[] t = s.toCharArray();
            for(int j = 0; j<t.length; j++)
                ss.add(t[j]-'a');
            cl[i] = s;
        }

        N = ss.size();
        indeg = new int[26];
        g = new ArrayList[26];
        for(int i = 0; i<26; i++)
            g[i] = new ArrayList<>();

        
        outer:
        for(int i = 0; i<M-1; i++){
            char[] a = cl[i].toCharArray();
            char[] b = cl[i+1].toCharArray();

            int min = Math.min(a.length, b.length);
            int j = 0;
            for(; j<min; j++){
                if(a[j] != b[j]){
                    g[a[j]-'a'].add(b[j]-'a');
                    indeg[b[j]-'a']++;
                    continue outer;
                }
            }
        }

        ArrayList<Integer> ans = new ArrayList<>();
        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0;
        for(int i : ss){
            if(indeg[i] == 0)
                q.add(i);
        }

        while(!q.isEmpty()){
            if(q.size() > 1){
                System.out.print("inf");
                return;
            }

            int ci = q.poll();
            ans.add(ci);
            cnt++;

            for(int n : g[ci]){
                if(--indeg[n] == 0)
                    q.add(n);
            }
        }

        if(cnt != N)
            System.out.print(-1);
        else{
            StringBuilder sb = new StringBuilder();
            for(int i : ans){
                sb.append((char)('a'+i));
            }
            System.out.print(sb);
        }
    }
}

사고의 흐름 및 풀이

임의의 사전순으로 정렬한 문자열이 M개 주어질 때, 그것을 보고 임의의 사전순 알파벳을 공백없이 출력하거나

해당 정보에 모순이 있으면 -1을 출력하고 만약 여러 사전순 정렬법이 존재한다면 inf를 출력하는 문제.

 

먼저 입력 전처리를 수행해서 정수 정점간의 간선 정보로 방향이 존재하는 그래프를 생성하고 

위상정렬을 수행해서 3가지 조건에 대해 걸러내면 될 것 같았다. 

 

입력 전처리의 경우 사전순으로 들어오게 되면 두 문자열을 비교해서 길이가 짧은 쪽 기준으로 각 문자를 비교한다.

만약 다른게 있으면 사전순이므로 a -> b의 간선 정보를 나타낸다. 이를 기록하고 break하고 끝내야 한다.

원래는

if(j == 0 || j == min)
    continue;
g[a[j-1]-'a'].add(b[j]-'a');
indeg[b[j]-'a']++;

이런 코드가 추가로 붙어있었는데 정리하면서 생각을 해 보니까 이건 붙여서는 안된다. 

한쪽이 더 긴건 뭐가 더 붙든간에 (정렬법상 의미가 없음) 사전순으로 늦게 되기 때문이다.

그래서 지웠는데 AC다. 있었을 때도 AC였는데 음..

-> 사전순에서 ab < abc인 이유는 ab가 abc의 접두사이기 때문이고 j == min인 경우는 바로 이 경우이다.

하지만 그렇다고 해서 b->c로 간선을 추가하게 되는건 올바른 정보 전달이 아니다.

-> 생각해보니 위의 조건때문에 아래 코드가 도달하지 않아서 AC 였다.

 

위상정렬에서 어떤 순간의 queue의 크기가 2 이상이면 두개로 갈라진다는 의미이므로 

DAG가 여러가지가 나올 수 있다는 의미이다. 따라서 이때 inf를 출력하고 종료한다.

위상정렬 후 cnt가 알파벳의 종류의 갯수와 다르면 모순이 발생했다는 것이므로 (사이클 발생) -1을 출력한다.

그 외에는 정상이므로 list에 저장한 알파벳을 순서대로 출력하면 끝.

---

문제 - 조건을 만족하는 수 (역그래프, 우선순위 큐)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-numbers-satisfying-specific-conditions/description

조건을 만족하는 수 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static char rc() throws IOException{
        sst.nextToken();
        return (char) sst.ttype;
    }

    static int N;
    static int[] indeg;
    static int[] indegR;
    static ArrayList<Integer>[] g;
    static ArrayList<Integer>[] gR;
    static ArrayList<Integer> ans = new ArrayList<>();
    static ArrayList<Integer> ansR = new ArrayList<>();

    static String itos(int x){
        String s = String.valueOf(x);
        int l = s.length();
        if(l == 3)
            return s;
        if(l == 2)
            return "0"+s;
        return "00"+s;
    }

    static void topoSort(boolean isR){
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i = 1; i<=N; i++){
            if(isR){
                if(indegR[i] == 0)
                    q.add(i);
            }
            else{
                if(indeg[i] == 0)
                    q.add(i);
            }
        }

        while(!q.isEmpty()){
            int ci = q.poll();
            if(isR){
                ansR.add(ci);
            }
            else{
                ans.add(ci);
            }

            if(isR){
                for(int n : gR[ci]){
                    if(--indegR[n] == 0)
                        q.add(n);
                }
            }
            else{
                for(int n : g[ci]){
                    if(--indeg[n] == 0)
                        q.add(n);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        indeg = new int[N+1];
        indegR = new int[N+1];
        g = new ArrayList[N+1];
        gR = new ArrayList[N+1];
        for(int i = 1; i<=N; i++){
            g[i] = new ArrayList<>();
            gR[i] = new ArrayList<>();
        }

        for(int i =1; i<N; i++){
            char cmd = rc();
            // 정방향 a->b
            // 역방향 b->a
            if(cmd == '<'){
                g[i].add(i+1);
                indeg[i+1]++;
                gR[i+1].add(i);
                indegR[i]++;
            }
            else{
                g[i+1].add(i);
                indeg[i]++;
                gR[i].add(i+1);
                indegR[i+1]++;
            }
        }
        topoSort(false);
        topoSort(true);

        StringBuilder sb = new StringBuilder();
        for(int x : ans){
            sb.append(itos(x));
        }
        sb.append("\n");
        for(int x : ansR){
            sb.append(itos(N-x+1));
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

1부터 N까지의 연속된 숫자가 있고 N-1개의 부등호가 차례로 주어질 때, 부등호의 대소관계를 모두 만족하는 수열 중

사전순으로 가장 작은 수열과 사전순으로 가장 큰 수열을 출력하는 문제이다. 

출력 포맷은 N이 최대 999이므로 앞에 0을 3자리 패딩을 유지하면서 출력해야한다.

-> 9 면 009, 13이면 013, 200이면 200 

 

일단 관찰을 해 보면, 부등호 자체는 대소관계이기 때문에 a < b라면 a 가 선행되어야 b가 될 수 있다 가 되고, 이를 이용해서 위상 순서를 정하게 되면 사전 순으로 가장 작은 수열은 정방향으로 부등호를 해석해서 그래프를 만들고 사전순으로 가장 작은 노드를 뽑는걸로 위상정렬에서 고정해놓고 위상정렬을 한 결과를 그대로 출력하면 된다. 

 

사전순으로 큰 수열의 경우에는 위상정렬에서 사전순으로 작은 정점을 우선해서 뽑기 때문에 

역그래프를 형성하고 그걸 따라 위상정렬을 하면 1번 정점에는 가장 큰 수가 와야 하므로

x가 정점 번호일 때, N - x + 1을 적절히 패딩해서 출력하면 된다.

 

구현 팁 : StreamTokenizer에서 부호들은 ttype으로 받는다. sval로 받지 않는다...

---

문제 - 새로 번호 매기기 (역그래프, 다시 풀기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-renumbering-process/description

새로 번호 매기기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] indeg;
    static ArrayList<Integer>[] g;
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();

        while(M-->0){
            int a = read();
            int b = read();
            g[b].add(a);
            indeg[a]++;
        }

        int cnt = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for(int i=1; i<=N; i++){
            if(indeg[i] == 0)
                q.add(i);
        }

        while(!q.isEmpty()){
            int ci = q.poll();
            ans.add(ci);
            cnt++;

            for(int n : g[ci]){
                if(--indeg[n] == 0)
                    q.add(n);
            }
        }

        if(cnt != N){
            System.out.print(-1);
            return;
        }

        int[] t = new int[N+1];
        int x = N;
        for(int i : ans){
            t[i] = x--;
        }
        StringBuilder sb = new StringBuilder();
        for(int i= 1; i<=N; i++){
            sb.append(t[i]).append(" ");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

N개의 정점과 M개의 간선 정보가 주어졌을 때, 주어진 간선 정보로 정점에 새 번호를 부여하려고 한다.

1) x->y로 가는 간선이 있다면 x 노드의 새로운 번호는 y 노드의 새로운 번호보다 작아야 한다.

2) 번호는 1번부터 N번까지 단 한번씩만 등장해야 한다.

위 2 조건을 모두 만족하는 정답중 사전순으로 가장 앞서는 답을 출력하는 문제이다.

 

이게 그냥 생각하면 위상정렬해서 위상 순서 순으로 작은거부터 값을 부여하면 되는거 아닌가 싶은데 이게 이렇게 하면

위상 순서 자체를 사전순 최소로 해주는거지 값을 새로 부여한 것을 사전순 최소로 하는 것이 아니다. 

그래서 관점을 바꿔서 생각하면 가장 큰 번호 N은 누구한테 줘야 할까? 를 생각해보자.

-> outdegree가 0인 정점만 가능하고 큰 번호는 가능한 한 인덱스가 큰 정점에게 부여해야

앞에 있는 정점들의 번호가 작아진다는 그리디한 결과를 얻게 된다.

-> sink ( outdegree가 0인 정점) 들 중에서도 인덱스가 큰 것에게 주어야 한다. 

-> 이게 구현할 때 PriorityQueue를 reverseOrder()로 해야하는 이유이다. 

 

그래서 역그래프를 생성하고 우선순위 큐도 큰 값 순서로 뽑아준 다음 N부터 큰 값 먼저 위상 순서 1번부터 부여하고

이렇게 정리한 값을 인덱스를 따라서 출력하게 되면 답이 된다.

---

문제 - 지질 연구 (스트렐러 하천 문제)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-geological-research/description

지질 연구 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] indeg;
    static ArrayList<Integer>[] g;

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i= 1 ;i<=N; i++)
            g[i] = new ArrayList<>();

        while(M-->0){
            int a = read();
            int b = read();
            g[a].add(b);
            indeg[b]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        // power[i] = i 지층이 받는 압력도
        int[] power = new int[N+1];
        Arrays.fill(power, 1);
        // maxpower[i] = i가 받는 현재 가장 큰 압력도 
        int[] mp = new int[N+1];
        // cnt[i] = i에 영향을 행사하는 가장 큰 압력도의 갯수
        int[] cnt = new int[N+1];
        for(int i = 1; i<=N; i++){
            if(indeg[i] == 0)
                q.add(i);
        }

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

            for(int n : g[ci]){
                if(power[ci] > mp[n]){
                    mp[n] = power[ci];
                    cnt[n] = 1;
                }
                else if(power[ci] == mp[n])
                    cnt[n]++;

                if(--indeg[n] == 0){
                    q.add(n);
                    if(cnt[n] > 1)
                        power[n] = mp[n]+1;
                    else if(cnt[n] == 1)
                        power[n] = mp[n];
                }
            }
        }

        int ans = -1;
        for(int p : power){
            ans = Math.max(ans, p);
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

N개의 정점과 M개의 간선이 존재하고, a->b 는 a가 b에게 압력을 가하고 있는 상태임.

아무 압력도 받지 않는 지층의 압력도는 1이고

어떤 지층이 압력을 받을 때 그중 가장 큰 압력을 기준으로 하는데

그 값의 갯수가 1개면 최대 압력이, 2개 이상이면 최대 압력 + 1이 현재 지층의 압력도가 된다.

-> Strahler Number (스트렐러 하천 순서) 문제라고 부른다

 

위상정렬에서 다음 노드를 뽑을 때 정점들 간의 최대 값을 갱신해준다. 

이때 압력도를 저장하는 배열, 최대 압력을 저장하는 배열, 해당 지층의 최대 압력의 갯수를 저장하는 배열을 둬서

-> 최대 압력이 갱신되면 cnt = 1, 이미 최대 입력과 같다면 cnt ++

그리고 진입차수가 0이 되어 큐에 들어갈 때 maxPower 값을 참고해서 해당 지층의 압력도를 갱신한다.

---

문제 - 조각 (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-assembly/description

조립 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] indeg;
    static ArrayList<int[]>[] g;

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i= 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        while(M-->0){
            int a = read();
            int b = read();
            int w = read();
            // a를 완성하려면 b가 w개 필요함
            g[b].add(new int[]{a,w});
            indeg[a]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        ArrayList<Integer> minPart = new ArrayList<>();
        // dp[i][j] = i번째 조각을 만들 때 필요한 기본부품 j의 갯수 (N+1*N+1)
        int[][] dp = new int[N+1][N+1];
        for(int i = 1; i<=N; i++){
            if(indeg[i] == 0){
                q.add(i);
                // 기본조각은 1개만 필요
                dp[i][i] = 1;
                minPart.add(i);
            }
        }

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

            for(int[] n : g[ci]){
                int ni = n[0];
                int nw = n[1];
                // ni 부품을 만들기 위해 ci 부품이 nw개만큼 필요함
                // dp[ci]의 int 배열은 ni를 만들기 위한 조립도니까 거기 모두한테 nw 곱해서 더해줘야함
                for(int k= 1; k<=N; k++){
                    dp[ni][k] += dp[ci][k]*nw;
                }

                if(--indeg[ni] == 0){
                    q.add(ni);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int x : minPart){
            if(dp[N][x] > 0)
                sb.append(x).append(" ").append(dp[N][x]).append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

N개의 부품이 있고 a,b,c 입력이 M개가 들어올 때 부품 a를 만들기 위해 부품 b가 c개 필요하다는 뜻임.

N번째 부품을 완성하기 위해 필요한 기본 부품이 각각 몇개씩 필요한지 출력하는 문제이다. 

-> 배열 상으로는 기본 부품 필요 없는건 0으로 저장되므로 출력할 때 1개 이상인 기본 부품만 출력해야 한다.

 

입력을 다시 보면 

b->a 인데 c개 필요니까 g[b].add(a, c) 의 형태가 되고 indegree[ a ] ++ 이다. 

-> 위상정렬을 할 때는 next 부품을 만들기 위해 ci를 만드는데 필요한 모든 기본 부품들이 nextW 개씩 만큼 필요하다는 뜻

 

그래서 dp의 정의는 다음과 같다.

dp [ i ] [ j ] = 부품 i를 만들기 위해 기본 부품 j가 몇 개 필요한지 저장 (크기는 N+1 * N+1)

진입차수가 0인 부품은 기본부품이므로 dp [ i ][ i ] = 1로 나타낸다. 

-> 자기 자신 하나만 필요하고 다른 부품들은 필요없어서 0

 

위상정렬 과정에서 ci -> ni, nw 를 처리할 때

dp [ next ] 의 모든 필요 부품에 dp [ ci ] 의 모든 구성 기본 부품 * nextW배만큼 해서 더해주면 된다. 

그렇게 갱신하고 next의 진입차수가 0이 되는 순간은 조립 순서(위상 순서)만을 나타내기 때문에

queue에는 int형 ni만 넣으면 된다.

---

문제 - 최대 방문 경로(다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximum-visitable-route/description

최대로 방문 가능한 경로 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] indeg;
    static ArrayList<Integer>[] g;
    static ArrayList<Integer>[] rg;
    static final int INF = Integer.MIN_VALUE;
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        rg = new ArrayList[N+1];
        for(int i =1 ; i<=N; i++){
            g[i] = new ArrayList<>();
            rg[i] = new ArrayList<>();
        }
        
        while(M-->0){
            int a = read();
            int b = read();
            g[a].add(b);
            rg[b].add(a);
            indeg[b]++;
        }

        ArrayList<Integer> order = new ArrayList<>();
        Queue<Integer> q = new ArrayDeque<>();
        for(int i = 1 ;i<=N; i++){
            if(indeg[i] == 0)
                q.add(i);
        }

        while(!q.isEmpty()){
            int ci = q.poll();
            order.add(ci);

            for(int n : g[ci]){
                if(--indeg[n]==0)
                    q.add(n);
            }
        }

        int[] dp1 = new int[N+1];
        dp1[1] = 1;
        for(int x : order){
            // 도달 못하는 정점은 못 감
            if(dp1[x] == 0)
                continue;

            for(int n : g[x]){
                dp1[n] = Math.max(dp1[n], dp1[x] + 1);
            }
        }

        Collections.reverse(order);
        // 역그래프 필요함
        int[] dp2 = new int[N+1];
        dp2[N] = 1;
        for(int x : order){
            if(dp2[x] == 0)
                continue;

            for(int n : rg[x]){
                dp2[n] = Math.max(dp2[n], dp2[x] + 1);
            }
        }

        if(dp1[N] == 0){
            System.out.print(-1);
            return;
        }

        int cur = 1;
        ans.add(1);

        while(cur != N){
            int min = Integer.MAX_VALUE;
            for(int n : g[cur]){
                // 정방향 위상 순서에서 그다음 정점이어야 하고
                if(dp1[n] != dp1[cur] + 1)
                    continue;
                // 최장경로 위 정점 조건 만족해야함
                if(dp1[n] + dp2[n] - 1 != dp1[N])
                    continue;
                
                min = Math.min(min, n);
            }
            ans.add(min);
            cur = min;
        }

        StringBuilder sb = new StringBuilder();
        sb.append(dp1[N]).append("\n");
        for(int x : ans){
            sb.append(x).append(" ");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

먼저 위상순서를 위상정렬로 order에 저장해 놓고 order에서의 연결된 간선을 따라서 dp를 전파한다.

 

dp1[i] = START -> i 의 최장거리 (정방향 그래프 + 위상순서)
dp2[i] = i -> DEST 의 최장거리 (역그래프 + 역위상순서)

어떤 정점 k 가 최대 정점 경로에 존재하려면 dp1[k] + dp2[k] -1 = dp1[N] 을 만족해야 함 

---

문제 - 동시 우선순위 건설

https://www.codetree.ai/ko/trails/complete/curated-cards/test-priority-construction/description

우선순위 건설 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[] indeg;
    static int[] time;
    static ArrayList<Integer>[] g;

    public static void main(String[] args) throws IOException{
        N = read();
        time = new int[N+1];
        indeg = new int[N+1];
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        for(int i = 1; i<=N; i++){
            time[i] = read();
            while(true){
                int cur = read();
                if(cur == -1)
                    break;
                g[cur].add(i);
                indeg[i]++;
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        // 동시에 지을 수 있다는 것은 최대값을 구하라는 것
        int[] dp = new int[N+1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        for(int i = 1; i<=N; i++){
            if(indeg[i] == 0){
                q.add(i);
                dp[i] = time[i];
            }
        }

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

            for(int n : g[ci]){
                if(dp[ci] != Integer.MIN_VALUE 
                    && dp[n] < dp[ci] + time[n]){
                    dp[n] = dp[ci] + time[n];
                }
                if(--indeg[n] == 0)
                    q.add(n);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i<=N; i++){
            sb.append(dp[i]).append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

동시에 건설할 수 있다는 건 서로 독립적인 작업은 병렬로 처리 가능하다는 뜻이다. 

따라서 선행 작업의 완료 시간 중 가장 늦게 끝나는 작업만 저장해두고 거기서 갱신하면 된다.