백준(C++) 1516번 게임 개발 풀이

C++로 구현한 2252번 줄 세우기 문제 풀이입니다.

 

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

1516번: 게임 개발

---

#include <iostream>
#include <vector>
#include <queue>
#define MAX 501

using namespace std;

int n, inDegree[MAX], result[MAX], time[MAX];
vector<int> a[MAX];

void topologySort() {
	queue<int> q;
	for(int i=1; i<=n; i++) {
		if(inDegree[i] == 0) {
			result[i] = time[i];
			q.push(i);
		}
	}
	for(int i=1; i<=n; i++) {
		int x = q.front();
		q.pop();
		for(int j=0; j<a[x].size(); j++) {
			int y = a[x][j];
			result[y] = max(result[y], result[x] + time[y]);
			if(--inDegree[y] == 0) {
				q.push(y);
			}
		}
	}
	for(int i=1; i<=n; i++) {
		printf("%d\n", result[i]);
	}
}

int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%d", &time[i]);
		while(1) {
			int x;
			scanf("%d", &x);
			if(x == -1) break;
			inDegree[i] ++;
			a[x].push_back(i);
		}
	}
	topologySort();
}

 

문제에서 건물의 종류 수 N 값의 범위가 500까지이기 때문에 MAX의 값을 501로 지정해준다.

 

메인코드에 건물의 개수를 입력받고 반복문 내에서는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야

 

하는 건물들의 번호를 입력받은 후 진입 차수를 1 증가시켜주고 정점을 연결시켜준다.

 

위상 정렬 알고리즘 수행에 해당하는 topologySort() 함수에서는 큐를 사용하도록 하며, 진입 차수가 0이라면 해당 건물을 

 

짓는데 걸리는 시간을 결과값에 넣고 그 정점을 큐에 삽입한다.

 

두번째 반복문에서 정점의 개수만큼 반복하도록 하고 큐에 가장 먼저 들어온 원소를 꺼낸 뒤 특정한 간선에 대해서

 

현재 도착지까지 가는 최소비용과 그 도착지로 가기 직전에 있는 정점을 지을 수 있는 최소비용 + 현재 그 도착지를 

 

짓는 시간을 비교하여 더 큰 값으로 갱신해준다.

 

그리고 새롭게 진입차수가 0이 된 정점을 큐에 삽입한다. 위와 같은 과정을 반복적으로 수행한다.

 

 

  * 위상 정렬 알고리즘 수행 과정 및 정보는 아래의 글에서 확인하시면 됩니다.

https://unie2.tistory.com/44

위상 정렬(Topology Sort)