https://www.acmicpc.net/problem/1516
1516번: 게임 개발
첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부
www.acmicpc.net
이 문제는 위상정렬로 풀 수 있는 문제이다. 위상 정렬은 주로 게임에서 스킬트리와 같은 즉, 선행되어야 하는 작업이 있을 때의 순서를 어떻게 처리해야 빠른지를 풀 때 사용하는 알고리즘이다. 위상정렬의 구현은 그래프 구조에서 in-direction 의 갯수를 저장하는 배열이 가장 핵심이다. 즉 어떤 노드 K 번에 들어오는 간선의 수가 3개가 있을 때, ind[K] = 3 처럼 저장한 뒤, ind[i] 값이 0인 정점부터 큐(queue)에 넣고 순차적으로 탐색해가면 된다.
위 그림으로 설명하면
1. ind 값이 0 인 1번 3번 노드가 queue에 넣는다.
2. 큐에 가장 앞에 있는 노드를 방문(1 번) 한 후, 이 노드에 연결된 (2 번으로의)간선을 돌면서 ind[ graph[cur][next] ] 의 값을 -1 해준다.
( 그림에선 2번으로의 간선이므로, ind[2]--; )
3. 만약 2번의 과정을 통해서 ind 값이 0 이 되면(ind[ graph[cur][next] ] == 0) 해당 노드를 queue에 push 한다.
4. 2~3번을 반복
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int inline max(int a, int b){return a>b?a:b;}
int n, t[501], ind[501], ans[501];
vector<int> v[501];
int main(){
scanf("%d", &n);
int p;
for(int i=1;i<=n;i++){
scanf("%d", &t[i]);
while(scanf("%d", &p) == 1){
if(p == -1) break;
v[p].push_back(i);
ind[i]++;
}
}
queue< pair<int, int> > q;
for(int i=1;i<=n;i++){
if(ind[i] == 0){
q.push(make_pair(i, t[i]));
ans[i] = t[i];
}
}
while(!q.empty()){
int cur = q.front().first;
int curt = q.front().second;
q.pop();
for(int i=0; i<v[cur].size(); i++){
ind[ v[cur][i] ]--;
ans[ v[cur][i] ] = max(ans[v[cur][i]], curt + t[ v[cur][i] ]);
if(ind[ v[cur][i] ] == 0){
q.push(make_pair(v[cur][i], ans[ v[cur][i] ] ));
}
}
}
for(int i=1;i<=n;i++){
printf("%d\n", ans[i]);
}
return 0;
}
|
cs |
'알고리즘 문제풀이' 카테고리의 다른 글
| BOJ 1305 광고 (0) | 2020.09.24 |
|---|---|
| BOJ 10826 피보나치 수 4 (0) | 2020.09.04 |
| BOJ 2407 조합 (0) | 2020.09.04 |
| LCS 최장 공통 부분 수열 (0) | 2020.09.03 |
| BOJ 가장 긴 증가하는 부분 수열 (0) | 2020.09.02 |