[C++] 백준(BOJ) 1005 - ACM Craft

- 문제

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

1005번: ACM Craft

 

- 문제 분석

1) N(건물 개수) : 2 ~ 1000

2) K(규칙 개수) : 1 ~ 100,000

3) 1 ≤ X, Y, W ≤ N

4) Di (i번째 건물의 건설 시간) : 0 ~ 100,000

각 건물을 지으려면 해당 건물을 짓기 위한 모든 선행 건물을 지어야 한다. (수강신청 커리큘럼과 비슷함)

이러한 구조의 순서를 찾기 위해서는 위상정렬(Topological Sorting)을 사용해야한다. 위상정렬을 통해 각 노드를 순회하면서 해당 건물을 완공하는 데에 걸리는 시간을 계산해야 한다.

 

- 풀이

문제의 조건인 모든 선행 건물을 짓고 해당 건물을 지을 수 있기 때문에 여러 선행 건물들 중 가장 마지막에 건설되는 건물이 다 지어지고 나서야 해당 건물을 지을 수 있다. 이를 간단하게 그려보면 다음과 같다.

 

하지만 위상정렬의 특성상 목표 건물을 기준으로 선행 건물을 쭉 순회하는 것이 아니라 진입 차수가 0인 것들을 하나씩 지워나가면서 순회를 하기 때문에 조금 까다로울 수 있다.

 

이때 DP적 관점에서 메모이제이션을 응용하면 간단하게 해결할 수 있다. 예를 들어 선행건물[1]의 진입 차수가 0이라 지워야 한다면 기존의 Complete[목표건물] 값과 Complete[선행건물[1]] + delay[목표건물] 값을 비교해 큰 것을 기록하는 방법이 있다.

이런 식으로 선행 건물이 모두 지워질 때까지 Complete 배열에 값을 기록해놓으면 최종적으로 목표 건물의 완공 시간이 남게 된다.

 

- 코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int n, k, w;		// n : 건물 개수, k : 순서 개수, w : 목표 건물
int delay[1001];	// 각 건물 건설 소요 시간
int complete[1001];	// 각 건물 완공 시간
int indegree[1001];	// 진입차수
vector<int> adjlist[1001];	// 간선리스트

void init() {
	// 이전 Test Case 값 지우기
	fill(delay, delay + 1001, 0);
	fill(complete, complete + 1001, 0);
	fill(indegree, indegree + 1001, 0);
	for (int i = 0; i <= 1000; i++) {
		vector<int>().swap(adjlist[i]);
	}

	// 입력 및 변수 초기화
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> delay[i];
	}
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		indegree[y]++;
		adjlist[x].push_back(y);
	}
	cin >> w;
}
void solve() {
	// 위상정렬 수행
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {		// 진입차수 0인 것들 q에 push
			q.push(i);
			complete[i] = delay[i];
		}
	}

	while (!q.empty()) {
		int now = q.front(); q.pop();
		if (now == w) return;		// 목표인 w값을 구하면 그냥 종료

		for (int& next : adjlist[now]) {
			complete[next] = max(complete[next], complete[now] + delay[next]);
			if (--indegree[next] == 0)
				q.push(next);
		}
	}
}

int main() {
	fastio;

	int tc; cin >> tc;
	for (int i = 0; i < tc; i++) {
		init();		// 입력
		solve();	// 문제 풀이
		cout << complete[w] << "\n";	// 출력
	}
}