2 분 소요

문제

문제 바로가기

입력

첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다)

둘째 줄에는 각 건물당 건설에 걸리는 시간 D1, D2, …, DN이 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다)

마지막 줄에는 백준이가 승리하기 위해 건설해야 할 건물의 번호 W가 주어진다.

출력

건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.

건설순서는 모든 건물이 건설 가능하도록 주어진다.

접근방법

문제에서 요구하는 것은 W을 완료하기까지 걸리는 최소 시간이다.

작업 간의 선후관계에 따라 그래프로 나타낼 수 있고, 이는 위상 정렬을 통해 해결할 수 있다. 위상 정렬 알고리즘은 DAG(Directed Acyclic Graph)에서 사용할 수 있으며, 각 노드의 진입 차수(in-degree)를 이용하여 구현할 수 있다.

  1. 각 노드의 진입 차수를 계산한다.
  2. 진입 차수가 0인 노드를 큐에 넣는다.
  3. 큐에서 노드를 꺼내 연결된 모든 간선을 제거하고 다음 노드의 totalTime값을 업데이트한다. totalTime은 각 노드까지 누적된 최대시간을 저장한다.
  4. 다음 노드의 진입 차수가 0이라면 큐에 넣는다.

큐가 빌 때까지 위의 과정을 반복하면 모든 노드의 totalTime값을 구할 수 있다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, k, w;
    static int[] time, totalTime, indegree;
    static List<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            time = new int[n + 1];
            totalTime = new int[n + 1];
            indegree = new int[n + 1];
            list = new ArrayList[n + 1];

            for (int i = 1; i <= n; i++) {
                list[i] = new ArrayList<>();
            }

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

            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                indegree[b]++;
                list[a].add(b);
            }

            w = Integer.parseInt(br.readLine());

            topologySort();

            System.out.println(totalTime[w]);
        }
    }

    public static void topologySort() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                totalTime[i] = time[i];
                q.offer(i);
            }
        }

        while(!q.isEmpty()) {
            int temp = q.poll();
            for(int i = 0; i < list[temp].size(); i++) {
                int next = list[temp].get(i);
                totalTime[next] = Math.max(totalTime[next], totalTime[temp] + time[next]);
                indegree[next]--;
                if(indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
    }
}

댓글남기기

참고