[99클럽/파이썬 챌린저/17일차] 작업

백준 2056번 작업 G4

 

문제
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다) 모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

입력
첫째 줄에 N이 주어진다.
두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업,..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력
첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

 

 

다이나믹 프로그래밍, 그래프 이론, 위상 정렬, 방향 비순환 그래

 

 

정석적인 위상 정렬 문제이다.

해당 알고리즘은 간단하지만 매우 효과적이다.

 

진행 방식은 다음과 같다.

1. 진입 차수가 0인 정점을 모두 큐에 넣는다.

2. 큐에서 꺼낸 정점의 최종 시간을 저장하고, 해당 정점에서 갈 수 있는 모든 정점들의 최대 시간을 갱신한다.

3. 이때 방문한 정점의 진입 차수를 1만큼 뺀다. 만일 진입 차수가 0이 되었다면 해당 정점을 큐에 넣는다.

4. 2를 반복한다.

 

시간 복잡도의 경우 O(V+E)이다.

V의 경우 최초 진입 차수가 0인지 확인하는 과정에서 발생한다.

E의 경우 모든 정점들의 간선을 탐색하는 과정에서 발생한다.

 

 

import sys
from collections import deque

n = int(sys.stdin.readline())
cost = [0] * (n+1)
dp = [0] * (n+1)
routes = [[] for _ in range(n+1)]
cnts = [0] * (n+1)

for num in range(1, n+1):
    info = list(map(int, sys.stdin.readline().split()))
    cost[num] = info[0]
    cnts[num] = info[1]
    for i in range(2, 2 + info[1]):
        routes[info[i]].append(num)

q = deque()

for i in range(1, n+1):
    if cnts[i] == 0:
        q.append(i)
        dp[i] = cost[i]

while q:
    v = q.popleft()
    for e in routes[v]:
        cnts[e] -= 1
        dp[e] = max(dp[e], dp[v] + cost[e])
        if cnts[e] == 0:
            q.append(e)
            
print(max(dp))​

 

 

#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <deque>

int dp[10001] = {0,};
int costs[10001] = {0, };
int cnt[10001] = {0, };
vector<int> routes[10001];



int main(void)
{
	int n; cin>>n;

	for (int i = 1; i <= n; ++i)
	{
		int cost; cin>>cost; costs[i] = cost;
		int k; cin>>k;
		while (k--)
		{
			int e; cin>>e;
			routes[i].push_back(e); ++cnt[e];
		}
	}
	

	deque<int> dq;
	for (int i = 1; i <= n; i++)
	{
		if (cnt[i] == 0) dq.push_back(i);
	}
	
	while (!dq.empty())
	{
		int v; v = dq.front(); dq.pop_front();
		dp[v] += costs[v];

		while (!routes[v].empty())
		{
			int vv; vv = routes[v].back(); routes[v].pop_back();
			dp[vv] = max(dp[vv], dp[v]);
			
			if(--cnt[vv] == 0) dq.push_back(vv);
		}
	}


	int result = 0;
	for (int i = 1; i <= n; i++)
	{
		result = max(result, dp[i]);
	}
	
	cout<<result;
}

 

 

---

 

좋아하는 문제가 나왔다.