[백준/C++] 1005번. ACM Craft

문제

1005번: ACM Craft

---

1. 마지막 풀이

사고 과정

위상정렬 공부하려고 집은 문젠데, DP 개념도 섞여 있는 문제.

 

둘을 동시에 진행할 수도 있지만, 내가 아직 위상정렬이 미숙해서 따로따로 구현하기로 했다.

 

알고리즘

이 문제는, 특정 건물을 지으면 다음 건물을 지을 수 있는 시스템에서 시작된다.

내가 특정 건물(예제 1의 4)을 짓고 싶은데, 이 건물을 가장 빠르게 짓는 방법을 알고 싶다.

 

건물을 짓기 위해선 선행 건물들을 모두 지어야 한다. 하지만 일꾼의 수는 무한해서, 건물은 동시에 지을 수 있다.

 

백준의 예제 사진

 

이 경우를 생각해보자. 우린 4번 건물을 지어야 한다.

 

이를 위해선 2, 3번 건물을 지어야 하며, 둘을 짓기 위해 1번 건물을 지어야 한다.

 

그럼 어떤 과정으로 진행되느냐?

1. 1번 건물을 짓는다(10초 소요)
2. 2, 3번 건물을 동시에 짓기 시작한다.
3. 2번 건물이 다 지어진다. (총 11초 소요)
4. 3번 건물이 다 지어진다. (총 110초 소요)
5. 따라서 게임 시작 110초 후 4번 건물을 지을 수 있으며, 4번 건물을 짓는데 10초가 소요된다.
6. 4번 건물까지 짓는데 시간은 120초가 걸린다.

여기서 DP인 부분을 찾자면, 짓는 시간이 갱신되는 부분이다. 이는 바텀업 방식으로 접근하면 좋을 것 같다.

1	2	3	4
0	0	0	0

 

 

1번을 지으며, 자기 자신, 연결된 2번, 3번 건물에 자신의 시간(10초)를 적어둔다.

1	2	3	4
10	10	10	0

 

2번 건물에. 역시나 자기 자신 칸엔 자신의 시간을 더하고, 그 후 연결된 건물엔 값을 자신의 값으로 갱신한다.

1	2	3	4
10	11	10	11

 

3번 건물에 접근, 똑같이 수행한다.

하지만 이때, 4번 건물에 접근하니 이미 누가 값을 써놨다. 둘 중 더 큰 값을 골라야 하므로, 3번 건물의 값을 덮어씌운다.

1	2	3	4
10	11	110	110

 

4번 건물에 접근, 동일하게 수행한다.

이때, 4번 이후 건물이 없으므로 종료된다.

1	2	3	4
10	11	110	120

 

이렇게 최소 시간을 구할 수 있다. 목표는 최소 시간, 갱신은 더 큰 값임에 주의하자.

 

그럼 DP는 알겠는데, 위상정렬은 왜 필요한가? 그리고 그게 뭔가?

---

25. 위상 정렬(Topology Sort)

위상정렬 개념이 너무 잘 설명돼있는 블로그... 이걸 보며 공부했다.

 

간단히 위상정렬을 설명하자면, 단방향 비순환 그래프(Directed Acyclic Graph, DAG)에서 쓰는 정렬 방식이다.

 

https://velog.io/@so_yeong/그래프-알고리즘-3.-위상정렬Topological-Sorting-vlittvru

사진 출처

 

정렬을 완료하면 이런 식으로 된다. (위상정렬은 답이 여러 개 나올 수 있다.)

 

나가는 간선만 있는 노드부터 시작해, 들어오는 간선만 있는 노드로 도달하는, 그리고 그 순서를 알려주는 정렬 방식이다.

 

구현도 단순하게, 처음 입력받을 때 그래프와 InDegrees(각 노드로 들어오는 진입차선의 개수)를 체크해두고,

진입차선이 없는 노드를 큐에 넣고,

큐가 빌 때까지 아래 과정을 반복한다.

• 큐에서 노드 하나를 꺼내, 새 배열에 넣는다. (이 배열이 정렬된 배열이 된다.)
• 해당 노드가 가리키는 모든 노드의 진입차수를 1씩 줄인다.
• 이 과정에서 진입차수가 0이 된 노드들을 다시 큐에 넣는다.

이를 통해 DAG에서, 순서를 얻을 수 있게 된다.

---

위 예시는 1 -> 2 -> 3 -> 4의 순서였기에 와닿지 않을 수 있다. 하지만 실제론, 어떻게 넘버링되어 있을지 알 수 없다.

예를 들어 같은 예제에서, 1번과 4번의 위치를 바꿔보자. 그래도 순차적 반복으로 DP를 하면 될까?

 

우린 선행 건물이 없는 건물부터, 선행 건물만 있는 건물 순서로 DP를 진행해야 한다. 이를 얻기 위해 쓰는 게 바로 위상정렬이다.

 

원래는 위상정렬 실행과 동시에 DP를 진행할 수도 있지만(이는 개선에 적어두겠다.), 여기선 개념을 확실히 잡기 위해

위상정렬 -> 정렬된 벡터 생성 -> 벡터에 저장된 순서대로 DP 실행으로 코드를 짜겠다.

 

코드

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

int n, k, w;

// dp (시간 계산)
std::vector<int> cost;
std::vector<int> min_cost;

// 위상정렬 (순서 지정)
std::vector<std::vector<int>> graph;
std::vector<int> inDegree;
std::queue<int> queue;

std::vector<int> sorted;

void input() {
	std::cin >> n >> k;
	
	cost.assign(n + 1, 0);
	min_cost.assign(n + 1, 0);

	graph.assign(n + 1, std::vector<int>(0));
	inDegree.assign(n + 1, 0);

	sorted.clear();

	for (int i = 1; i <= n; ++i) {
		std::cin >> cost[i];
	}

	int a1, a2;
	while (k--) {
		std::cin >> a1 >> a2;
		graph[a1].push_back(a2);
		++inDegree[a2];
	}

	std::cin >> w;
}

void topologySort() {
	for (int i = 1; i < inDegree.size(); i++) {
		if (inDegree[i] == 0) {
			queue.push(i);
		}
	}

	int a;
	while (queue.empty() == false) {
		a = queue.front();
		queue.pop();

		sorted.push_back(a);

		for (int i : graph[a]) {
			if (--inDegree[i] == 0) {
				queue.push(i);
			}
		}
	}
}

int minCost() {
	for (int a : sorted) {
		min_cost[a] += cost[a];

		for (int i : graph[a]) {
			if (min_cost[a] > min_cost[i]) {
				min_cost[i] = min_cost[a];
			}
		}
	}

	return min_cost[w];
}

int main() {
	int t;
	std::cin >> t;

	while (t--) {
		input();

		topologySort();

		std::cout << minCost() << "\n";
	}
}

 

입력, 위상정렬, DP(minCost)를 함수로 나눠놨기에, 하나씩 살펴보면 어렵지 않을 것이다.

 

결과

 

결과는 꽤 널널하게 성공.

---

개선

사고 과정

아마 코드를 보면 그런 생각이 들었을 거다. sorted 배열이 꼭 필요한가? 그냥 정렬된 순간, DP를 같이 실행하면 되지 않나?

 

그리고 그 해답은 여기 있다.

 

코드

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

int n, k, w;

// dp (시간 계산)
std::vector<int> cost;
std::vector<int> min_cost;

// 위상정렬 (순서 지정)
std::vector<std::vector<int>> graph;
std::vector<int> inDegree;
std::queue<int> queue;

void input() {
	std::cin >> n >> k;
	
	cost.assign(n + 1, 0);
	min_cost.assign(n + 1, 0);

	graph.assign(n + 1, std::vector<int>(0));
	inDegree.assign(n + 1, 0);

	sorted.clear();

	for (int i = 1; i <= n; ++i) {
		std::cin >> cost[i];
	}

	int a1, a2;
	while (k--) {
		std::cin >> a1 >> a2;
		graph[a1].push_back(a2);
		++inDegree[a2];
	}

	std::cin >> w;
}

void topologySort() {
	for (int i = 1; i < inDegree.size(); i++) {
		if (inDegree[i] == 0) {
			queue.push(i);
		}
	}

	int a;
	while (queue.empty() == false) {
		a = queue.front();
		queue.pop();

		sorted.push_back(a);

		min_cost[a] += cost[a];

		for (int i : graph[a]) {
			if (--inDegree[i] == 0) {
				queue.push(i);
			}

			if (min_cost[a] > min_cost[i]) {
				min_cost[i] = min_cost[a];
			}
		}
	}
}

int main() {
	int t;
	std::cin >> t;

	while (t--) {
		input();

		topologySort();

		std::cout << min_cost[w] << "\n";
	}
}

 

이렇게, 위상정렬을 진행하며 큐에서 뽑은 순간, DP를 함께 실행하면 코드를 더 줄일 수 있고, 불필요한 메모리도 줄일 수 있다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/29395398

jinhan814님의 코드. 역시나 위상정렬과 DP가 쓰이면서 알고리즘은 동일하다.

 

내 코드와 비교

하지만 재밌는 부분이 있었는데, 바로 아래 부분이다.

while (q.size()) {
...
}

 

나는 보통 여기에 while (q.empty() == false)를 쓰는데, 이렇게 쓸 수도 있다는 게 신기했다.

 

다만 이게 더 낫냐?라고 물으면, 글쎄. 치는 사람 입장에서야 편하겠지만, 뜻이 직관적으로 와닿지는 않는다. 난 계속 empty() == false를 쓸 것 같다.

---

강평

위상정렬과 DP가 섞여 있어 재밌는 문제인데, 위상정렬을 처음 배우려 이 문제를 골랐다는 게 재밌기도 하다. (집어보니 이거였지만.)

위상정렬은 방법이 정해져 있어서, BFS처럼 한 번 배워두면 유사한 문제는 싹 다 풀렸다. 많이 도움되는 친구.