[BOJ1005번 : ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

분류 : 위상 정렬

import java.io.*;

import java.math.*;

import java.util.*;



class Myscanner {

    BufferedReader br;

    StringTokenizer st;



    public Myscanner() {

        br = new BufferedReader(new InputStreamReader(System.in));

    }



    String next() {

        while (st == null || !st.hasMoreElements()) {

            try {

                st = new StringTokenizer(br.readLine());

            } catch (IOException e) {

                e.printStackTrace();

            }

        }

        return st.nextToken();

    }



    int nextInt() {

        return Integer.parseInt(next());

    }



    long nextLong() {

        return Long.parseLong(next());

    }



    double nextDouble() {

        return Double.parseDouble(next());

    }

}



public class Main {

    public static Myscanner sc = new Myscanner();

    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));



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



        int TC = sc.nextInt();



        while (TC-- > 0) {

            int N = sc.nextInt();

            int M = sc.nextInt();

            int[] Time = new int[N+1];

            int[] idg = new int[N+1];

            int[] result = new int[N+1];

            Vector<Integer>[] Vector = (Vector<Integer>[]) new Vector[N+1];

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

            for (int i = 1; i <= N; i++) {

                Vector[i] = new Vector<Integer>();

            }

            for (int i = 1; i <= N; i++) {

                Time[i] = sc.nextInt();

            }

            for (int i = 0; i < M; i++) {

                int X = sc.nextInt();

                int Y = sc.nextInt();

                Vector[X].add(Y);

                idg[Y]++;

            }

            int W = sc.nextInt();

            for (int i = 1; i <=N; i++) {

                if (idg[i] == 0) {

                    result[i] = Time[i];

                    q.offer(new se(i));

                }

            }



            for (int i = 1; i <= N; i++) {

                se s = q.poll();

                int curr = s.s;

                for (int next : Vector[curr]) {

                    result[next] = Math.max(result[next], result[curr] + Time[next]);

                    if (--idg[next] == 0)

                        q.offer(new se(next));

                }

            }            

            out.println(result[W] + " ");

        }

        out.flush();

    }

}



class se implements Comparable<se> {

    int s;



    se(int s) {

        this.s = s;

    }



    @Override

    public int compareTo(se o) {

        return s <= o.s ? -1 : 1;

    }

}

1005번 문제. 항상 보면서 이건 어떻게 풀까 하다가 도전도 안 하고 포기한 문제.

그러다 이번에 종 만북 깊이 우선 탐색 부분을 공부하면서 위상 정렬에 대해서 배웠다.

단순히 책만으로는 이해가 되지 않아서 검색을 통해 코드를 많이 봤고 아무래도 위상 정렬 문제는 정형화된 코드가 있는 거 같다.

 

Vector, List, ArrayList 3가지를 이용해서 제출해봤는데 Vector가 메모리도 적고 시간도 좀 더 빠르게 나왔고

물론 내 코드보다 더 빠르게 하는 방법도 있겠지만 아직은 잘 모르겠다