[백준] 1005번 ACM Craft 문제풀이 방법 feat. 자바

ACM Craft 문제풀이 방법 feat. 자바

문제

 

알아야 할 알고리즘 지식

위상정렬(Topological_Sort)

• 간단하게 말하자면, 방향이 있는 그래프를 정렬하는 것이다. 
• 전후관계가 분명한 문제에서 방향이 있을 경우, 어떤 것이 먼저 사용될 수 있는지를 파악하여 문제를 풀어나가는 알고리즘이다.
• 추후, 위상정렬에 관한 알고리즘 포스팅 예정

 

 

문제풀이방법

 

1.  글을 읽어보면, 건물을 건설하는데 순서가 있다고 한다. ex) 1번의 건물의 걸설이 완료되면, 2번과 3번의 건물을 건설할 수 있다. 
   
   • 이와 같은 경우, 방향이 존재한다. ( 1번다음엔 2번, 3번으로 가는 경우만 있다. 즉, 2번에서 1번으로 갈수 있는 경우는 없다. )
   • 전후관계가 분명하다. 
   • 전후관계가 없을 수도 있다. 이 경우에는, 언제 건설이 되어도 상관이 없다는 말이다. 즉, 처음으로 세워도 무관한다.
2. 전후관계를 파악한 후, 언제 건설을 하건 상관이 없는 노드를 Queue에 집어 넣어준다.

이 그림과 같은 경우엔, 맨 처음에 1만 큐에 들어간다.

 

 

  3.  1을 큐에서 꺼내서 1과 연결되어 있는 2, 3의 값을 갱신해준다. 갱신한 후, 만약 2에 들어올 연결이 더이상 없다면 2를 큐에 넣어준다. ( 3도 마찬가지 )

 

 

  4. 건설시간을 구할 때는 MAX의 값을 구해야한다.

• 왜 MAX 값을 구해야 하는가?
  • 위의 그림에서 5 -> 2로 들어오는 노드가 하나 더 있다고 가정해보자. ( 5의 값은 50 )
  • 그렇다면, 2는 무조건 1 과 5 의 뒤에 나타나야한다.

 

 

소스코드

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 ACMCraft_1005 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

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

            int[] node = new int[N];
            int[] time = new int[N];
            int[] result = new int[N];
            ArrayList<Integer>[] arr = new ArrayList[N];

            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++) {
                arr[i] = new ArrayList<>();
                time[i] = Integer.parseInt(st.nextToken());
            }

            int s,e;
            for(int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
                s = Integer.parseInt(st.nextToken());
                e = Integer.parseInt(st.nextToken());

                arr[s-1].add(e-1);
                node[e-1]++;
            }

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

            Queue<Integer> qu = new LinkedList<>();
            for(int i=0; i<N; i++) {
                if(node[i] == 0) {
                    result[i] = time[i];
                    qu.add(i);
                }
            }

            for(int i=0; i<N; i++) {
                int b = qu.poll();

                for(int index : arr[b]) {
                    result[index] = Math.max(result[index], time[index] + result[b]);
                    if(--node[index] == 0){
                        qu.add(index);
                    }
                }
            }

            System.out.println(result[W-1]);
        }
    }
}

 

 

 

문제링크

www.acmicpc.net/problem/1005

1005번: ACM Craft