[백준] 알고리즘 분류(그래프 이론,JAVA)1005번, ACM Craft

문제 링크

1005번: ACM Craft

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 건물을 짓는 순서는 정해져 있으며, 각각 완공되는 시간이 존재합니다.

2. 건물 순서는 모든 건물이 완공될 수 있도록 주어집니다.

3. 목표 건물을 완공되는 최소 시간을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 위상 정렬을 통해서 목표 건물이 완공되도록 탐색합니다.

 

3. 목표 건물이 완공되었을 때 시간을 결과로 출력합니다.

 

각 지역 최단 거리 탐색!

 

 

위상 정렬을 통해서 목표 건물을 완성하는 최소 시간을 구합니다.

위상정렬 - 위키백과, 우리 모두의 백과사전

 

 

예를 들어 아래와 같은 상황일 때

	2	3	5	7	8	9	10	11
child	1	0	0	0	2	2	2	2

 

child가 0일 때 건물을 시공 가능!

 

Why?

 

해당 건물을 가리키는 자식 건물들이 모두 완공되었다고 판단할 수 있기 때문입니다.

 

{3, 5, 7} 건물 완공!

 

	2	3	5	7	8	9	10	11
child	1	0	0	0	0	2	0	2

 

{8, 9} 건물 완공!

 

 

....

 

이러한 방식으로 건물을 완공해 나아가며 목표 건물(W)가 완공되었을 때 시간을 결과로 출력하면 됩니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

※1번째 테스트케이스만 진행되는 과정을 보여드리겠습니다.

 

N : 4

M : 4

 

건물 완공 시간 : { 10, 1, 100, 10}

 

건물 관계 정보

	1	2	3	4
child	0	1	1	2

 

2. 위상 정렬을 통해서 목표 건물이 완공되도록 탐색합니다.

 

위상 정렬을 이용한 탐색 진행!

child 0 : { 1 } 

 

1 → 2 : 10초

 

1 → 3 : 10초

 

	1	2	3	4
child	0	0	0	2

child 0 : { 2, 3 } 

2 → 4 : 11초

 

3 → 4 : 110초

 

 

	1	2	3	4
child	0	0	0	0

child 0 : { 4 } 

4 : 120

 

※4에 도착해서 건설을 시작한 것은 3 → 4로 왔을 때 이므로 110 + 10 = 120이 완공되는 시간입니다.

 

목표 건물 4 완공!

 

 

3. 목표 건물이 완공되었을 때 시간을 결과로 출력합니다.

 

 

120 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 건물의 관련된 정보들을 띄어쓰기 기준 나누었습니다.
• 위상 정렬을 이용하여 각 건물의 완공시간을 구합니다.
• 목표 건물이 완공되었을 때 시간을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //width : 건물 완공 시간, count : child 수, answer : 각 건물 완공 시간
    static int[] width, count, answer;
    static ArrayList<ArrayList<Integer>> graph;	//건물간 관계 저장 리스트
    public static void main(String args[]) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        //각 테스트 케이스 진행!
        for(int test_case = 0;test_case < T;test_case++) {
            st = new StringTokenizer(br.readLine()," ");
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            width = new int[N+1];
            count = new int[N+1];
            graph = new ArrayList<>();
            for(int i=0;i<=N;i++)
                graph.add(new ArrayList<>());
            st = new StringTokenizer(br.readLine()," ");
            //건물 완공 시간 저장
            for(int i=1;i<=N;i++)
                width[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());
                count[B]++;	//child 개수 증가!
                graph.get(A).add(B);
            }
            int W = Integer.parseInt(br.readLine());
            Queue<Integer> q = new LinkedList<>();	//시공할 건물 저장 Queue
            answer = new int[N+1];
            //child 0개 확인
            for(int i=1;i<=N;i++) {
                answer[i] = width[i];	//각 건물 시간 초기화
                if(count[i] == 0)	//0개일 때 Queue 저장
                    q.offer(i);
            }
            //위상 정렬 진행!
            while(!q.isEmpty()) {
                int cur = q.poll();
                //해당 건물 완공 후 연결된 건물 탐색
                for(int next : graph.get(cur)) {
                    answer[next] = Math.max(answer[next], answer[cur] + width[next]);
                    count[next]--;	//child 감소
                    if(count[next] == 0)	//child 0이면 시공 진행하도록 Queue 저장
                        q.offer(next);
                }
            }
            bw.write(answer[W] + "\n");	//목표 건물 W의 완공 시간 BufferedWriter저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }

}