[BaekJoon] 1005번 ACM Craft (Java) 문제 풀이 [Gold 3]

문제

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

1005번: ACM Craft

 

어떻게 풀 것인가?

처음에 문제를 보았을 때 난처했다.

무엇을 말하고자 하는지 잘 모르겠다는 생각이 들어서, 아래에 알고리즘 분류를 참고하였다.

위상정렬?? 이라고 하는 알고리즘에 대해서 공부하게 되었다.

 

백준 알고리즘 분류

그래프가 주어졌을때, 노드마다 연결된 간선에 방향이 존재하고, 어떤 특정한 노드를 방문하기 위해서는 해당 노드에 진입 가능 이후에 방문이 가능할때 위상정렬을 사용한다고 한다.

 

위 문제와 적합한 조건이다.

 

위와 같은 조건에 부합할 때 노드를 방문하는 순서를 찾아야 한다면 위상정렬을 사용할 수 있다.

 

위상 정렬의 과정은 다음과 같다.

1. 그래프의 각 노드들의 진입 차수 테이블 생성 및 진입 차수 계산
2. 진입 차수가 0인 노드 큐에 넣기 (이때 어떤 노드 먼저 시작하던지 관계없음)
3. 큐에서 노드를 하나 꺼낸 후 꺼낸 노드와 간선으로 연결된 노드들의 진입 차수 감소 (진입 차수 테이블 갱신)
4. 진입 차수 테이블을 갱신 후 진입 차수의 값이 0인 노드가 있다면 큐에 넣기 (없으면 아무것도 안 함)
5. 3~4번의 순서를 큐에 더 이상 아무것도 없을 때까지 반복

이에 3 ~4번 과정을 진행할 때 time 배열을 이용하여 노드에서 건물을 짓는데에 걸리는 시간을 계산하여 비교하였다.

그리고 큰 값을 가진 건물을 더해주었다.

 

풀면서 놓쳤던점

https://codingnojam.tistory.com/66

[Algorithm] 위상정렬(Topological Sort)을 Java로 구현해보자!!

위상 정렬의 경우 위 블로그를 참조하였다.

 

이 문제를 통해 얻어갈 것

위상정렬에 대한 이해.

 

내 코드 

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

// 백준알고리즘 1005번 ACM Craft
public class Main {
    static int T;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int test_case = 1; test_case <= T; test_case++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

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

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

            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < N + 1; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 1; i <= N; i++) {
                time[i] = Integer.parseInt(st.nextToken());
            }

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

            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                graph.get(start).add(end);
                edgeCount[end]++;
            }

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

            // 위상정렬에 사용할 큐
            Queue<Integer> q = new LinkedList<>();
            int[] result = new int[N + 1];

            // 진입차수가 0인 값 큐에 넣기
            for (int i = 1; i <= N; i++) {
                result[i] = time[i];

                if (edgeCount[i] == 0) {
                    q.offer(i);
                }
            }

            while (!q.isEmpty()) {

                int nodeNo = q.poll();

                for (int i : graph.get(nodeNo)) {
                    result[i] = Math.max(result[i], result[nodeNo] + time[i]);
                    edgeCount[i]--;

                    if (edgeCount[i] == 0) q.offer(i);
                }
            }

            sb.append(result[w]).append("\n");

        }
        System.out.println(sb);
    }
}