백준 2056. 작업

🅰 백준 2056. 작업

2056번: 작업

✏️ 문제 풀이

• 순서가 주어지므로 위상정렬의 개념을 이용하여서 풀었다.
• 일단 위상정렬이랑 비슷하지만 선행관계가 없는 작업들은 동시에 수행되기 때문에 이 부분을 생각해내는데 시간이 조금 걸렸다.
• pq에 저장되는 정점들은 comparable을 이용하여 수행시간이 작은 순으로 정렬을 시켜서 하나씩 뽑아낸다.
• pq에는 들어오는 간선이 없는 정점부터 저장을 해서 탐색을 시작한다.
• cur = pq.poll() 한 정점이 걸리는 시간을 ans에 반복해서 저장시켜준다.
• 1. 만약 pq에 정점이 2개이상 있다면 (동시에 수행가능한 작업들이 있다면) cur의 시간만큼을 빼준 뒤 큐에 다시 넣어줘야 한다. (그래야 시간 중복이 안일어난다)
  • 큐에서 빼서 다시 큐에 넣어줘야 하기때문에 임시리스트 temp에 동시수행 가능한 정점만큼 cur의 시간을 빼준 뒤 저장해두고 나중에 큐에 다시 넣어주었다.
• 2. 이제 cur과 연결된 정점들 중 들어오는 간선이 1인(cur 하나뿐인) 노드들을 탐색하여 pq에 넣어준다
  
  • cur이 가리키는 정점들은 cur과의 간선이 끊어지기 때문에 connect[node.vertex]--; 를 해서 연결된 간선 수를 최신화 시켜준다.
• 3. 임시리스트 temp에 저장해 둔 정점들을 다시 pq에 넣어주고 임시리스트는 temp.clear()를 통해 초기화 시켜준다.
• 큐가 빌때까지 반복해서 수행하다 보면 ans에 최소 시간이 저장된다.

✏️ 소스코드

package graph;

import java.util.*;
import java.io.*;

class Node implements Comparable<Node> { // 시간 순으로 정렬되도록 comparable 해줌
	int vertex;
	int time;

	Node(int v, int t) {
		vertex = v;
		time = t;
	}

	@Override
	public int compareTo(Node e) {
		return this.time <= e.time ? -1 : 1;
	}

}

public class Main_골드4_2056_작업 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선 순위 큐에 저장하여 시간이 적은 순으로 정점 탐색
		ArrayList<Node> list[]; // 인접 리스트 구현
		LinkedList<Node> temp = new LinkedList<>(); // 선행관계가 없는 작업들 동시 수행시 시간 차감을 위한 temp리스트
		int N = Integer.parseInt(br.readLine());
		int connect[] = new int[N + 1]; // 위상정렬을 하기위한 정점으로 들어오는 간선 수 체크
		int time[] = new int[N + 1]; // 작업마다 걸리는 시간 저장
		list = new ArrayList[N + 1];
		for (int i = 0; i <= N; i++) { // 인접리스트 초기화
			list[i] = new ArrayList<>();
		}

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st.nextToken());
			int relation = Integer.parseInt(st.nextToken());
			time[i] = T; // i번 작업에서 걸리는 시간 저장
			for (int j = 0; j < relation; j++) { // 선행관계에 있는 작업들의 수만 큼 
				int next = Integer.parseInt(st.nextToken());
				list[next].add(new Node(i, T)); // list에 저장
				connect[i]++; // i로 들어오는 간선 수 ++
			}
		}
		for (int i = 1; i <= N; i++) { // 들어오는 간선이 없는 정점먼저 탐색
			if (connect[i] == 0) {
				pq.add(new Node(i, time[i]));
			}
		}
		int ans = 0;
		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			ans += cur.time;
			while (!pq.isEmpty()) { // 동시 작업이 가능한 정점이 있을 경우
				Node next = pq.poll();
				temp.add(new Node(next.vertex, next.time - cur.time)); // 임시 리스트에 적게 걸리는 시간만큼 빼준 정점 저장
			}
			for (Node node : list[cur.vertex]) { // cur과 연결된 노드 중 
				if(connect[node.vertex] == 1) pq.add(node); // 들어오는 정점이 1개인 노드 pq에 저장
				connect[node.vertex]--;	// node.vertex에 cur.vertex 끊어지므로 간선 수--; 
			}
			for (Node node : temp) { // 시간 최신화 한 노드 큐에 다시 저장
				pq.add(node);
			}
			temp.clear(); // 임시 리스트 초기화
		}
		System.out.println(ans);
	}
}

 

✅ 후기

• 위상정렬을 이용한 문제집, 줄세우기보다 생각할게 많은 문제였는데 골드 4라니, 살짝 놀랬다.
• 하지만 하나하나 풀어서 쓴 후 생각한대로 코딩을 하니 정답을 맞출 수 있었다.