[BOJ1005] ACM Craft

[BOJ1005] ACM Craft

문제 링크

문제 설명

• 건물을 지을 때, 연결된 앞 건물들이 모두 지어지고나서 지을 수 있다.

• 건물 w의 번호를 입력했을 때, w가 지어지는데 걸리는 시간을 출력하는 문제이다.

풀이 과정

• 에지가 아닌 정점에 가중치가 있는 문제이다. -> 배열을 이용하여 노드 번호마다 가중치 값을 저장해 둠.

• 건물을 짓는데 있어서 현 건물을 짓기위해서는 연결된 다른 건물들이 짓고나서 지을 수 있으므로, 사이클이 없는 방향 그래프가 된다. (사이클이 있다면 각각의 건물들에 대한 위상이 무너짐)

• 즉, 위상정렬을 한 후 DAG에 대해 한 정점의 indegree에 이어진 정점들을 짓는데 걸리는 시간 + 현 건물을 짓는데 걸리는 시간들 중 가장 큰 값을 dp배열에 저장한다.

• 여기서 헷갈리지 말아야 할 부분이 특정 건물을 짓는데 드는 최소시간을 구한다고 해서 dp에 최소값이 저장되는 것이 아닌, 하나의 건물을 짓기 위해 지어야 하는 건물들이 다 지어져야 이 건물을 지을 수 있는 것이기 때문에, dp에는 최대 시간이 저장된다. 즉 longest path문제인데 가중치가 정점에 주어진 문제가 된다.

• DAG에서의 longest path 문제는 쉽게 풀 수 있으므로 dp를 이용하여 해결하였다.

코드

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

vector <vector <int>> adj;
vector <vector <int>> from_vert;
queue <int> q;
int check[1005];
int vert[1005];
int ind[1005];
int topological[1005];
int dp[1005];
int idx;

void bfs() {
	while (!q.empty()) {
		int now = q.front();
		check[now] = 1;
		topological[idx++] = now;
		q.pop();
		int size = adj[now].size();
		for (int i = 0; i < size; i++) {
			int next = adj[now][i];
			ind[next]--;
			if (ind[next] == 0) q.push(next);
		}
	}
}
int main() {
	int T, N, K,w;
	scanf("%d", &T);
	while (T--) {
		idx = 0;
		scanf("%d%d", &N, &K);
		adj.resize(N + 1);
		from_vert.resize(N + 1);
		for (int i = 1; i <= N; i++) {
			int weight;
			scanf("%d", &weight);
			vert[i] = weight;
		}
		for (int i = 0; i < K; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			adj[a].push_back(b);
			from_vert[b].push_back(a);
			ind[b]++;
		}
		for (int i = 1; i <= N; i++) {
			int size = from_vert[i].size();
			if (size == 0) q.push(i);
		}
		bfs();
		for (int i = 0; i < N; i++) {
			int size = from_vert[topological[i]].size();
			if (size == 0) {
				dp[topological[i]] = vert[topological[i]];
			}
			else {
				dp[topological[i]] = vert[topological[i]];
				for (int j = 0; j < size; j++) {
					dp[topological[i]] = max(dp[topological[i]], dp[from_vert[topological[i]][j]] + vert[topological[i]]);
				}
			}
		}
		scanf("%d", &w);
		printf("%d\n", dp[w]);
		adj.clear();
		from_vert.clear();
		memset(ind, 0, sizeof(ind));
		memset(check, 0, sizeof(check));
		memset(topological, 0, sizeof(topological));
		memset(dp, 0, sizeof(dp));
		memset(vert, 0, sizeof(vert));
	}
	return 0;
}

코드 리뷰

• 코드가 조금 지저분한 것 같은데 다음에 풀때는 예쁘게 짜봐야겠다.

• DAG에서의 Longest Path라는 조건을 찾은 것에 뿌듯.

• 수업시간에 배운 내용을 적용할 수 있어서 좋았다.

---