<유사문제 - 위상정렬>
1005 ACM Craft https://www.acmicpc.net/problem/1005 (더 직관적, 더 쉬움)
2623 음악 프로그램 https://www.acmicpc.net/problem/2623(dfs방식, cycle)
2056 작업 https://www.acmicpc.net/problem/2056
주어진 예시를 변경하여 다음과 같은 예를 들어보자.
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 2 -1
이 그래프는 사실상 다음과 같은 형태를 가질 것이다.
(굵은 검정글씨는 정점번호, 흰글씨는 최소 생산시간(갱신안됨))
1. 이 문제에서의 입력을 위의 형태로 구현할 수 있을 까?
할 수는 있겠지만 매우 번거롭고 시간도 많이걸릴것이다.
(4번정점과같이 연결되는 모든 정점을 표시할때도 있지만 5번정점과같이 인접한 정점만 표시할때도 있기때문에)
2. 그렇다면 입력을 진입차수와 인접리스트로 표현할 수 있을까?
이것또한 할 수 는 있지만 약간의 의문점이 생길것이다.
정점 4번을 예로들면 직접적으로 연결된 정점은 3번뿐이지만 정점1번도 입력으로 주어졌기 때문에 진입차수와 인접리스트는 2개가 될 것이다. (실질적으론 1개)
이렇게 진입차수가 정확하지 않은데 우리가 구하고자 하는 위상정렬을 할 수 있을까?
정답은 "할 수 있다" 이다. 그 이유는 직접 bfs를 돌리며 알아보도록 하겠다.
int cost[501]; //생산 시간
int indegree[501]; //진입차수
vector<int> vec[501]; //인접리스트
int ans[501]; //최소 생산 시간
| cs |
먼저 진입차수가 0인지점부터 queue에 삽입해 bfs를 돌린다.
이때 2, 3, 4의 최소 생산 시간을 갱신하는데 갱신하는 조건은 다음과같다.
$ans[V] = max(ans[V], ans[prev]+cost[V])$
즉, 정점 V번의 최소생산시간은 정점 V번으로 들어오는 값들 중 가장 큰 생산시간 + V번 생산 시간이다. 이것은 정점2, 3이 진입차수가 0이 될때 설명하겠다.
그다음 진입차수가 0인지점인 2, 3에서 bfs를 돌린다.
여기서 정점5번이 갱신되는데 생각해보면 정점5번은 3번이 14초만에 건설된다 할지라도 2번이 완성되야 건설할 수 있기 때문에 이들중 최댓값에서 선택해야되는 것이다.
이것은 위에 제시했던 의문점또한 해결된다.
정점 4번을 예시로 들면 1번과 인접하지않지만 인접리스트로 받았음에도 불구하고 이전값보다 더 큰값이 들어오면 갱신되므로 상관이 없어진다.
마지막으로 정점 4, 5에서 bfs를 돌리지만 인접리스트가 없기때문에 결과적으로는 전부 갱신되었다.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int N;
int cost[501];
int ans[501];
int indegree[501];
vector<int> vec[501];
void bfs(){
queue<int> q;
for (int n = 1; n <= N; n++){
if (indegree[n] == 0){
q.push(n);
ans[n] = cost[n];
}
}
while (!q.empty()){
int nedge = q.front();
q.pop();
for (int m = 0; m < vec[nedge].size(); m++){
int e = vec[nedge][m];
ans[e] = max(ans[e], ans[nedge] + cost[e]);
if (--indegree[e] == 0)
q.push(e);
}
}
}
int main(){
scanf("%d", &N);
for (int n = 1; n <= N; n++){
int edge;
scanf("%d", &cost[n]);
while (scanf("%d", &edge), edge != -1){
vec[edge].push_back(n);
indegree[n]++; //진입차수
}
}
for (int n = 1; n <= N; n++)
printf("%d\n", indegree[n]);
bfs();
for (int n = 1; n <= N; n++)
printf("%d\n", ans[n]);
return 0;
}
| cs |
