C++ ACM Craft 문제 풀기 (백준 1005)

 

읽어주셔서 감사합니다. 오늘은 백준의 1005번, ACM craft 문제에 대해 풀어보도록 하겠습니다.

*이번 문제는 1005번이라는 번호와는 걸맞지 않게 알고리즘을 사용합니다. 저도 굉장히 놀랍군요. 앞에서 6번쨰 문제에 BFS, DFS도 아닌 위상 정렬 문제를 내다니

---

code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX(x, y)	(((x) > (y)) ? (x) : (y))
#define MIN(x, y)	(((x) < (y)) ? (x) : (y))

using namespace std;

//this can replace with dynamic allocation, but static allocation is fore fit at KOI style
int Bt[1010]; //Builnding time
int flow[1010];
int dist[1010];

void solve(void) {
	int N, K, W;
	int cur, memA, memB;

	queue<int> next;
	vector< vector<int> > graph;

	cin >> N >> K; //first inp, graph, graph resize
	graph.resize(N + 1);

	flow[0] = dist[0] =  0;
	for (int i = 1; i <= N; i++) {  //second inp, init
		cin >> Bt[i]; 
		graph[0].push_back(i);
		flow[i] = 1; //instead of memset()
		dist[i] = 0; //instead of memset()
	}
	for (int i = 0, a, b; i < K; i++) {  //third input, form graph
		cin >> a >> b; 
		graph[a].push_back(b);
		flow[b]++;
	}
	cin >> W; //last input

	next.push(0); // start calculation
	while (!next.empty()) { // instead of "for(int i = 0;i < N;i++) {" or "while(1) {" but, if you use "while(1) {", you must code "if(cur == W) { break }" in loop
		cur = next.front();
		next.pop();

		if (cur == W) { break; } //just for speed. this make source ignore value of dist[node] that calculated after dist[W]

		memA = graph[cur].size();
		for (int i = 0; i < memA; i++) {
			memB = graph[cur].at(i);
			flow[memB]--;
			dist[memB] = MAX(dist[memB], dist[cur] + Bt[memB]); // instead of if(dist[memB] < dist[cur] + Bt[memB]) { dist[memB] = dist[cur] + Bt[memB]; }
			if (!flow[memB]) { 
				next.push(memB); 
			}
		}
	}
	
	cout << dist[W] << endl;
	return;
}

int main(void) {
	int T;
	cin >> T;
	for (int Tc = 0; Tc < T; Tc++) {
		solve();
	}
	return 0;
}

---

describe

이번 문제는 간단한 위상정렬 문제입니다.

"위상" 정렬이라는 알고리즘이 상대적으로 어려워서 그렇지, 이를 배우고 나면 쉬운 문제로 느껴지실 겁니다.

 

위상 정렬의 원리는 다음과 같습니다. 아주 많이 축약한 간략한 설명이니, 자세한 내용을 알고자 하는 분들은 아래를 참고하지길 바랍니다.

Geeks for Geeks Topological sort(English)

위상정렬 위키백과(한국어)

 

1) 각 node(건물)을 지을때 미리 visit(건설) 해야 하는 node(건물)수를 flow[node 번호]에 저장
2) flow[node 번호]가 0인 노드를 찾아, 그 노드를 건설함
3-1) 2와 다른 어떤 node(건물)를 지을때 미리 지어야 되는 건물에 2에서 찾은 node(건물)가 포함된다면, flow[3에서 찾은 node 번호]를 1 감소시킴
3-2) 동시에, 3에서 찾은 node[건물]을 건설하는데 걸리는 시간 dist[node 번호]는 dist[2에서 찾은 node 번호] + 3에서 찾은 건물을 짓는데 걸리는 시간의 최댓값으로 저장함.
4) 2와 3을 반복.

 

의 과정을 반복하며, 어떤 node(건물)에 도달하는데 걸리는 시간 dist[node number]를 도출해내는 겁니다.

---

사용방법

백준 1004번 참고

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

1005번: ACM Craft

 

---

실행화면

프로그램의 사용 목적을 고려하여 실행화면은 생략하도록 하겠습니다.