백준 문제 풀이 (1005번) java

문제

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

풀이

이 문제는 방향은 있으며 사이클이 없는 그래프 문제이다.(DAG 알고리즘 문제) 그래서 위상 정렬을 사용하여 문제를 해결하였다. 간선이 0인 번호의 빌딩은 먼저 지어져야 하는 빌딩이 없다는 것을 의미하므로 해당 빌딩까지 걸리는 시간은 그 빌딩이 걸리는 시간과 같다.

time[간선이 0인 빌딩의 인덱스] == timeSum[간선이 0인 빌딩의 인덱스]

위상 정렬을 수행하는 알고리즘은 크게 두 가지 스택(Stack)과 큐(Queue) 두 가지가 존재한다. 이 문제는 큐를 이용하여 풀었으며 입력 값으로 주어지는 건물의 순서를 받을 때 아래와 같이 list[x]에 y값을 추가시키고 count배열의 y번째 값을 증가시켜 y번째 빌딩의 간선의 수를 증가시킨다. count배열은 간선의 수를 체크하려고 만들었다. 만약 x번째 빌딩이 간선이 존재하지 않고 list[x].size()도 0이 아니라면 x번째 빌딩이 어떤 빌딩을 지을 때 먼저 지어야 하는 빌딩이라는 것을 의미한다.

for (int p = 0; p < K; p++) {

	st = new StringTokenizer(br.readLine(), " ");
	int x = Integer.parseInt(st.nextToken());
	int y = Integer.parseInt(st.nextToken());

		list[x].add(y);
		count[y]++;
	}

그리고 topologySort()메서드를 만들어서 메서드 안에 큐를 생성하여 간선이 0인 빌딩(인덱스)를 큐에 넣는다.

만약 간선의 수가 0인 빌딩이 없다면 사이클이 있다는 뜻이고 위상 정렬은 시작점이 존재해야 사이클이 생기는 그래프에서는 시작점을 찾을 수 없어 위상 정렬을 사용할 수 없다.

while문으로 큐가 비었는지 확인한 후 비어있지 않으면 큐에서 poll()메서드로 큐에 저장된 첫번째 값을 반환하고 제거한다. poll메서드로 반환한 값을 currentTime에 넣으면 currentTime에는 간선이 0인 빌딩의 인덱스 값이 담기게 된다. 해당 인덱스 빌딩(currentTime)을 먼저 지어야하는 빌딩으로 하는 빌딩의 인덱스들이 list[currentTime]안에 저장되어 있다. nextTime에는 list[currentTime]안에 저장된 값들을 담긴 순으로 받아서 timeSum[currentTime] + time[nextTime]와 timeSum[nextTime] 중 큰 값으로 timeSum[nextTime]값을 바꿔준다. timeSum[nextTime]를 비교하는 이유는 현재 nextTime 값의 간선의 수(count[nextTime])이 1보다 크다면 timeSum[nextTime]값은 처음에는 timeSum[currentTime] + time[nextTime]로 값을 가지겠지만 count[nextTime]--;되어도 count는 0이 안되므로 다시 한번 값이 바뀌게 되므로 count가 1보다 클 경우를 생각하여 다음처럼 비교하도록 코드를 작성하였다.

 for (int i = 0; i < list[currentTime].size(); i++) {
	int nextTime = list[currentTime].get(i);
	timeSum[nextTime] = Math.max(timeSum[currentTime] + time[nextTime], timeSum[nextTime]);
	count[nextTime]--;
	if (count[nextTime] == 0) {
			q.offer(nextTime);
	}

그리고 Math.max로 하는 이유는 문제 예시로도 알 수 있지만 1번 건물을 완성하고 2,3번 건물을 동시에 짓기 시작해도 2,3번의 최대시간(Max)이 끝나기 전까지는 4번 건물을 지을 수 없기 때문에 max로 코드를 작성한 것이다.

이렇게 코드를 작성하면 주어진 건물순서 규칙을 모두 계산하여 각 건물을 짓는 최소 시간을 구할 수 있게 된다.

코드

package Category;

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 q_1005 {

    static int[] time;
    static int[] timeSum;
    static ArrayList<Integer>[] list;
    static int[] count;

    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());


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

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

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

            time = new int[N + 1];
            list = new ArrayList[N + 1];
            st = new StringTokenizer(br.readLine(), " ");

            for (int j = 1; j <= N; j++) {
                time[j] = Integer.parseInt(st.nextToken());
                list[j] = new ArrayList<>();
            }

            count = new int[N + 1];

            for (int p = 0; p < K; p++) {

                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                list[x].add(y);
                count[y]++;
            }

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

            timeSum = new int[N + 1];
            topologySort();
            sb.append(timeSum[W]).append("\n");
        }
        System.out.println(sb);


    }


    static void topologySort() {

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < count.length; i++) {

            if (count[i] == 0) {

                timeSum[i] = time[i];
                q.offer(i); // 값을 추가
            }
        }

        while (!q.isEmpty()) {
            int currentTime = q.poll(); 
            for (int i = 0; i < list[currentTime].size(); i++) {

                int nextTime = list[currentTime].get(i);
                timeSum[nextTime] = Math.max(timeSum[currentTime] + time[nextTime], timeSum[nextTime]);
                count[nextTime]--;
                if (count[nextTime] == 0) {
                    q.offer(nextTime);
                }
            }
        }
    }
}