[백준] 1005번 ACM Craft C++ 문제풀이

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

1005번: ACM Craft

문제 풀이

위상정렬이라는 걸 처음 알게 되었다.

위상정렬이란 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘이다.

예를 들어 위의 문제에서 2번 건물을 건설하기 위해서는 1번을 건설해야하고, 4번 건물을 건설하기 위해서는 1,2,3번 건물이 세워줘야하는 것 처럼 말이다. 

위상정렬 알고리즘은 비순환 방향 그래프에서 사용할 수 있다. 즉 끝이 존재해야 위상 정렬을 사용할 수 있는 것이다.

 

위상정렬은 아래의 과정을 거친다.

  ① 진입차수가 0인 정점을 큐에 삽입합니다.
  ② 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.
  ③ 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다.
  ④ 큐가 빌 때까지 2번 ~ 3번 과정을 반복.

모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과가 된다. [출처 : "나동빈님 블로그"]

 

여기서 진입 차수라는 개념은 특정 노드로 들어오는 간선의 개수를 의미한다.

소스 코드

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

int indegree[1001] = { 0 }; // 진입차수
int cost[1001] = { 0 }; // 건물 건설 비용
int result[1001] = { 0 }; //그 노드에 도달하는데 필요한 총 비용

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int n, k;
		cin >> n >> k;
		//건물 건설 비용
		for (int j = 1; j <= n; j++) {
			cin >> cost[j];
			result[j] = cost[j];
		}

		vector<int> build[1001]; // node에 대한 배열
		// 건물 규칙
		for (int j = 0; j < k; j++) {
			int st, en;
			cin >> st >> en;
			build[st].push_back(en);
			indegree[en] += 1;
		}

		int w;
		cin >> w;
		
		queue<int> q;
		// 진입차수가 0인 노드를 queue에 넣음.
		for(int j = 1; j <= n; j++){
			if (indegree[j] == 0)
				q.push(j);
		}
		//위상정렬 수행
		while (!q.empty()) {
			// idx 노드는 진입차수가 0인 노드.
			int idx = q.front();
			q.pop();
			// idx노드와 연결된 노드들 탐색
			for (int j = 0; j < build[idx].size(); j++) {
				int dy = build[idx][j]; //idx 노드와 연결된 노드
				result[dy] = max(result[dy], result[idx] + cost[dy]);
				indegree[dy] -= 1;
				if (indegree[dy] == 0)
					q.push(dy);
			}
		}

		cout << result[w] << '\n';

		//초기화
		for (int j = 1; j <= n; j++) {
			indegree[j] = 0;
			cost[j] = 0;
			result[j] = 0;
		}
	}
}