[G3] 백준 1005번 ACM Craft C++ 위상 정렬

리뷰

 

위상 정렬을 통해 가중치가 있는 간선을 갖고 특정 노드의 최소값을 구하는 문제

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

 

문제 풀이

1. 테스트 케이스의 개수 tc, 노드의 개수 n, 간선의 개수 m, 목표 노드 dest를 전역변수로 초기화 해준다.
2. 인접 리스트를 담을 정수형 벡터 path, 각 노드의 소요시간 정보 times의 크기를 n의 최대값으로 설정해 준다.
3. init 함수를 통해 times 배열 초기화, path 백터를 초기화 해준다.
4. input 함수를 통해 n, m값과 각 노드의 소요시간, 간선정보, 목표 노드를 입력 받는다.
5. solution 함수를 통해 dest 노드가 건설이 완료 되기까지의 최소 시간을 출력해 준다.
6. cnt, sum 벡터를 n + 1 크기로, 초기값은 0으로 초기화 해준다.
7. 1 ~ n노드를 탐색하며 i번째 노드의 인접 리스트를 순회하며 인접한 노드의 cnt를 1씩 증가시켜 준다.
8. 정수형 큐 q를 초기화 해주고 cnt가 0인 노드를 큐에 추가해 주고, i번째 sum값을 자신의 times으로 초기화 해준다.
9. while 루프를 돌며 cnt가 0인 노드들을 뽑아준 뒤 해당 인접리스트의 노드들의 cnt를 1씩 빼준다.
10. 그리고 현재까지의 자기 자신까지의 소요 시간보다 이전 노드 + 자신의 소요시간이 크다면 갱신해 준다.
11. cnt가 0이 되었을 경우 next에 추가해 주면 된다.
12. 큐가 모두 빌때까지 탐색을 진행하고 sum의 dest 인덱스를 리턴하고 그걸 출력해 주면 된다.

 

참고 사항

없음

 

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

int tc, n, m, dest;
vector<int> path[1001];
int times[1001];

void init() {
	memset(times, 0, sizeof(times));
	for (int i = 1; i < 1001; i++) path[i].clear();
}

void input() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> times[i];
	while (m--) {
		int a, b; cin >> a >> b;
		path[a].push_back(b);
	}
	cin >> dest;
}

int solution() {
	vector<int> cnt(n + 1, 0);
	vector<int> sum(n + 1, 0);
	
	for (int i = 1; i <= n; i++) {
		for (int node : path[i]) cnt[node]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (!cnt[i]) {
			q.push(i);
			sum[i] = times[i];
		}
	}

	while (!q.empty()) {
		int node = q.front(); q.pop();
		
		for (int next : path[node]) {
			sum[next] = max(sum[next], sum[node] + times[next]);
			if (--cnt[next] == 0) q.push(next);
		}
	}
	return sum[dest];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> tc;
	while (tc--) {
		init();
		input();
		cout << solution() << "\n";
	}
}