[BOJ: 1005/ JAVA] ACM Craft

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

 

백준 1005번 문제 사진

1. 문제 요약

특정 건물을 가장 빨리 지을 때까지 걸리는 최소 시간을 알아내는 프로그램 

 

※ 주의할 점 

최소 시간을 알아내는 프로그램 이라지만, 동시에 건축을 해야하는 건물의 경우 
그 건물들이 모두 건축이 완성되어야 다음 건물을 건축할 수 있기 때문에 최소 시간을 그리 신경쓸 필요 없는 듯 하다. 

 

---

 

2. 알고리즘 (접근 방법) 

○ 위상 정렬 방식 (Queue) 

 

여기서 정점은 건축물을 말하는 것이며, 진입차수는 해당 건축물과 연결된 이전 건축물과의 간선이 몇개인지를 말하는 것이다. 

1005번 사진에서는 1, 2, 3, 4 건축물들이 모두 정점임을 의미하고, 1번 정점이 3번 정점과 연결되어 있고 이를 간선이라고 표한다. 
여기서 3번 정점으로 들어오는 진입차수는 1번과 연결된 간선 1개이다. 
또 다른 예로 4번 정점으로 들어오는 진입차수는

- 3번에서 들어오는 간선 1개

- 2번에서 들어오는 간선 1개

총 2개의 진입차수를 갖고 있다. 

 

1. 위상 정렬 방식으로 먼저 세팅을 해준다. 

• 진입차수가 0인 모든 정점을 Queue 에 삽입

for(int v = 1; v < V+1; v++) {
    if(inDegree[v] == 0) { // 진입차수가 없다면 방문을 해볼까나 
        q.add(v);
    }
}

 

• Queue 가 공백이 될 때까지 반복 수행 

while(!q.isEmpty()) {
	// ... 로직 
}

• 반복문 내에서 Queue 안에 있는 원소를 꺼내 해당 노드에서 나가는 간선(즉, 진입차수)을 그래프에서 제거한다.

int curr = q.poll(); // 큐에 담긴 맨앞에꺼 꺼내기 
    List<Integer> list = adjList[curr]; 

    // curr 인접한 정점을 순회하면서 간선 제거
    for(int i = 0; i < list.size(); i++) {
        int next = list.get(i); // 2, 3

        // curr 과 인접한 정점의 진입차수를 하나씩 제거 해주기 
        inDegree[next]--;

        //...다음 로직 
}

• 반복문 내에서 새롭게 진입차수가 0이 된 노드를 Queue 삽입한다.

if(inDegree[next] == 0) {
    q.add(next);
}

 

 

2. 반복문 내에서 인접한 정점을 건축하는 시간 (only 해당 정점의 건축시간) 과 해당 정점까지 오는데 걸린 건축시간과 비교하여 누적값을 넣어준다. 

 

↓ 예시 더보기 클릭 

현재 정점 (curr 변수에 담긴 값) 와 인접한 정점(list.get(i) 해서 나오는 next 변수에 담긴 값) 을 건축하는 시간과

그 인접한 정점까지 오는데 걸린 시간을 합한 것이 bt 이다.

예를 들자면,

현재 정점은 3번이며, 인접한 정점은 4번인 상황이다. 

4번 정점까지 오는데 있어서 1 → 3 → 4 순으로 왔다면 

- times[next] = 4번 정점을 짓는 건축시간 10초

- result[curr] = 3번 정점 건축물까지 짓는데 걸린 건축시간 110초 (10 + 100) 

총 120 초가 된다. 

result[next] 에 담긴 값은 현재 times[next] 에 담긴 값과 같기에 

- 10초 < 120초 비교하여 120 초가 resutl[next] 에 들어가게 되는 구조이다.

// 차수가 갱신된 건물을 짓는데 걸리는 시간 
int bt = times[next] + result[curr];
result[next] = Math.max(bt, result[next]);

 

 

3. 최종 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); 
		StringBuilder sb = new StringBuilder();
		for(int t = 0; t < T; t++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken()); // 건물 개수 (정점의 개수) 
			int E = Integer.parseInt(st.nextToken()); // 건설 순서 규칙 개수 (간선의 개수) 
			
			ArrayDeque<Integer> q = new ArrayDeque<>(); 
			int[] times = new int[V+1];  
			List<Integer>[] adjList= new ArrayList[V+1]; 
			int[] inDegree = new int[V+1];
			int[] result = new int[V+1];
			
			st = new StringTokenizer(br.readLine());
			for(int v = 1; v < V+1; v++) {
				int time = Integer.parseInt(st.nextToken());
				times[v] = time; 
				result[v] = time;  
				adjList[v] = new ArrayList<>();				  
			}
			
			for(int e = 0; e < E; e++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken()); // 정점 1
				int to = Integer.parseInt(st.nextToken());   // 정점 2 (진입차수를 받는 정점) 
				
				adjList[from].add(to); 		// 유향 리스트 
				inDegree[to]++; 			// 진입차수 세팅 
			}
			
			// 건축해야할 번호 받기 
			int W = Integer.parseInt(br.readLine());
			
			for(int v = 1; v < V+1; v++) {
				if(inDegree[v] == 0) { // 진입차수가 0 인 정점을 큐에 추가
					q.add(v);
				}
			}
			
			// 큐가 공백이 될때까지 돌리기
			while(!q.isEmpty()) {
				int curr = q.poll(); // 큐에 담긴 정점 꺼내기
				List<Integer> list = adjList[curr];  // 해당 정점과 연결된 다음 정점들 리스트
				
	        	// curr 인접한 정점을 순회하기 
				for(int i = 0; i < list.size(); i++) {
					int next = list.get(i); 
					
                    // 인접한 정점의 진입차수 감소 시키기
					inDegree[next]--;
					
                    // 진입차수가 0이 되었다면, 큐에 담기 
					if(inDegree[next] == 0) {
						q.add(next);
					}
		         	// 차수가 갱신된 건물을 짓는데 걸리는 시간 
					int bt = times[next] + result[curr];
                    // 위에서 계산한 값과 기존에 가지고 있는 값 중 큰 값을 누적 값에 저장
					result[next] = Math.max(bt, result[next]);
				}
				
			}
            
            // 특정 건물 (W) 를 짓는데 걸리는 시간 출력 
			sb.append(result[W]).append("\n");
		}
		
		// 결과 출력
		System.out.println(sb);
	}

}