[BOJ/C++] 1005(ACM CRAFT)

1. Link

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

• 위상 정렬을 하도 안 다뤘더니 너무 어렵습니다.. 다만 코딩테스트가 코앞이라 준비하는 중에 감을 찾아 다행이라 생각할 따름입니다.
• 골드 내에서 위상 정렬은 유형의 특이성 덕에 유형 파악은 빠르게 될 수 있습니다. 대신에 구현 조건을 상세하게 파악하고, 자칫 중첩되어 연산될 수 있는 부분이 있는지 등 주의할 점은 염두에 두는 것이 좋습니다.

2. 풀이 과정

1. 그림이 곧 힌트입니다.(단방향 그래프 & acyclic) -> 위상 정렬
2. 이전의 건물이 모두 완성되어야 건설을 시작할 수 있음 -> 위상 정렬

• 위상 정렬은 다음과 같은 순서로 진행이 됩니다.
  1. 자신을 가리키지 않는 점을 확인합니다.

  2. 확인한 점을 가져와 해당 점으로부터 시작하는 연결다리와 함께 제거합니다.(--indeg[] == 0은 이 과정에 해당합니다.)
  3. 큐에 다른 점이 있을 경우 1번으로 돌아가 과정을 반복합니다.

• indeg 배열이 0이 될 때에 비로소 제한이 풀리는 것을 염두하지 않고 무작정 push 후 비교를 하면 중첩비교가 꽤나 많이 됩니다. 이 점을 감안하고 풀지 않을 시 메모리 초과가 발생하니 주의하시기 바랍니다.(경험담)

  if (--indeg[nxt] == 0) {
          q.push(nxt);
  }

3. 정답 코드

#include<iostream>
#include<queue>
using namespace std;

int t, n, m, w;
int indeg[1001], cost[1001], dist[1001];
vector<int> v[1001];

void input() {
	cin >> n >> m;
	int a, b;
	for (int i = 1; i <= n; ++i) {
		cin >> cost[i];
		indeg[i] = 0;
		dist[i] = cost[i];
		v[i].clear();
	}
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		v[a].push_back(b);
		++indeg[b];
	}
	cin >> w;
}

void solution() {
	input();
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (indeg[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int nxt : v[cur]) {
			if (--indeg[nxt] == 0) {
				q.push(nxt);
			}
			dist[nxt] = max(dist[nxt], dist[cur] + cost[nxt]);
		}
	}
	cout << dist[w] << '\n';
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		solution();
	}
	return 0;
}

4. Reference

https://en.wikipedia.org/wiki/Topological_sorting