[G4] 백준 10282번 해킹 C++ 다익스트

리뷰

 

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

간단한 다익스트라를 통해 최단 시간을 찾는 문제

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• n : 컴퓨터의 개수를 저장할 변수
• d : 의존성의 개수를 저장할 변수
• c : 해킹당한 컴퓨터의 번호를 저장할 변수
• edges : 간선 정보를 저장할 2차원 벡터
• Pos : 시뮬레이션에 사용할 노드 번호 node, 진행 시간 t를 정의할 구조체, t를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

pair<int, int> dijkstra()

 

다익스트라를 통해 감염된 컴퓨터의 개수와 마지막 컴퓨터가 감염되기까지 걸리는 시간을 구하기 위한 함수

1. Pos타입의 우선순위 큐 pq를 초기화 하고, 초기 감염된 컴퓨터 c와 시작 시간 0을 push해준다.
2. n + 1크기의 벡터 dist를 초기화 하고, 초기값은 매우 큰 값 20억을 할당한다.
3. 초기 컴퓨터의 번호의 dist값을 0으로 초기화 해준다.
4. pq가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
5. 해당 요소의 인접리스트를 순회하고, 현재 시간 + 간선의 가중치가 다음 노드의 dist값보다 작다면 갱신해 주고 pq에 push해준다.
6. while 루프가 종료된 후 변수 max_val과 cnt를 0으로 초기화 해준다.
7. dist를 순회하며 거리가 20억이 아니라면 cnt를 증가시키고, max_val보다 크다면 갱신해 준다.
8. 최종적으로 cnt, max_val을 리턴해 준다.

 

문제풀이

1. t를 입력 받고, t번의 while루프를 돌려준다.
2. 매 테케마다 n, d, c를 입력 받고, 벡터 edges를 clear 후 n + 1크기로 resize해준다.
3. d개의 간선 정보를 입력 받아 단방향 간선으로 추가해 준다.
4. dijkstra 함수를 호출 후 리턴 값을 ans에 저장해 준다.
5. ans에 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

• 예제에서 볼 수 있듯 컴퓨터 간의 의존관계는 단방향이다.

 

정답 코드

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

int t, n, d, c;
vector<vector<pair<int, int>>> edges;
struct Pos {
	int node, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};

pair<int, int> dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ c, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[c] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cur = pos.node, t = pos.t;
		if (dist[cur] < t) continue;

		for (auto& next : edges[cur]) {
			if (dist[next.first] > t + next.second) {
				dist[next.first] = t + next.second;
				pq.push({ next.first, t + next.second });
			}
		}
	}

	int max_val = 0;
	int cnt = 0;
	for (int i : dist) {
		if (i != 2e9) {
			cnt++;
			max_val = max(max_val, i);
		}
	}
	return { cnt, max_val };
}

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

	cin >> t;
	while (t--) {
		cin >> n >> d >> c;
		edges.clear();
		edges.resize(n + 1);

		while (d--) {
			int cn, nn, w; cin >> cn >> nn >> w;
			edges[nn].push_back({ cn, w });
		}

		auto ans = dijkstra();
		cout << ans.first << " " << ans.second << "\n";
	}
}