알고리즘 공부/C++

[G2] 백준 17835번 면접보는 승범이네 C++ 다익스트라

마달랭 2025. 4. 12. 20:52

리뷰

 

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

큐에 요소를 삽입하는 과정에서 N크기만큼 pq에 삽입하여 시간 초과를 받았다.

 

 

전역 변수

  • N : 도시 관련 배열의 최대 크기를 정의할 상수 변수
  • n : 도시의 개수를 저장할 변수
  • m : 간선의 개수를 저장할 변수
  • k : 면접장의 개수를 저장할 변수
  • K : 면접장이 위치한 도시의 번호를 저장할 배열
  • Edge : 간선 정보를 정의할 구조체
  • edges : 간선 정보를 인접리스트로 정의할 벡터 배열
  • P : 시뮬레이션 정보를 정의할 구조체, 거리를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

pair<int, ll> dijkstra() {
	priority_queue<P> pq;
	vector<ll> dist(n + 1, 1e11);
	for (int i = 0; i < k; ++i) {
		pq.push({ K[i], 0 });
		dist[K[i]] = 0;
	}

	while (!pq.empty()) {
		P p = pq.top(); pq.pop();
		int cn = p.cn;
		ll cv = p.cv;
		if (dist[cn] < cv) continue;

		for (const Edge& next : edges[cn]) {
			int nn = next.nn;
			ll nv = next.nv;
			
			if (dist[nn] > cv + nv) {
				dist[nn] = cv + nv;
				pq.push({ nn, cv + nv });
			}
		}
	}
	auto it = max_element(dist.begin() + 1, dist.end());
	return { it - dist.begin(), *it };
}

 

다익스트라를 수행하여 면접장으로 부터 가장 먼 도시의 번호와 거리를 구하는 함수

 

문제풀이

  1. n, m, k값을 입력 받고, m개의 단방향 간선을 edges배열에 저장해 준다. 단, b와 a를 서로 바꾸어 준다.
  2. k개의 면접장 도시 번호를 입력 받아 K배열에 입력해 준다.
  3. dijktra함수를 호출하여 P타입의 우선순위 큐 pq를 초기화 해준다.
  4. 정수형 벡터 dist를 n + 1크기로, 값은 10억보다 크게끔 초기화 해준다.
  5. K배열을 순회하며 각 면접장 도시 번호와 초기 거리 0을 pq에 삽입해 주고, 해당 번호의 dist값을 0으로 변경한다.
  6. pq를 순회하며 다익스트라 알고리즘을 통해 각 도시로 이동할 수 있는 최단 거리를 구해준다.
  7. 변수 it에 max_element함수를 통해 dist에서 가장 큰 값의 이터레이터를 저장해 준다.
  8. it의 인덱스와 값을 리턴해 준 뒤 해당 값을 변수 res에 저장해 준다.
  9. res에 저장된 값을 순차적으로 줄바꿈을 통해 출력해 준다.

 

트러블 슈팅

  1. pq에 K배열의 값을 추가해 줄때 k개의 요소가 아닌 foreach로 추가하여 pq가 터져 시간 초과를 받았다.
  2. k개의 요소만 pq에 삽입, dist의 거리를 0으로 저장하여 AC를 받았다.

 

참고 사항

  1. 각 도시에서 면접장이 아닌 면접장에서 도시까지의 최단 거리를 구해주어야 한다.
  2. 이를 위해 인접 리스트를 초기화 할 때 도시 번호를 역순으로 변경하여 저장해 주어야 한다.
  3. max_element를 사용할 때 dist.begin() + 1부터 수행해 주어야 dist[0]에 담긴 매우 큰 값을 무시할 수 있다.
  4. 혹은 dist[0]을 0으로 초기화 후 dist의 begin()부터 end()까지 순회해 주면 된다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 100001;
int n, m, k;
int K[N];
struct Edge {
	int nn;
	ll nv;
};
vector<Edge> edges[N];
struct P {
	int cn;
	ll cv;
	bool operator<(const P& other) const {
		return cv > other.cv;
	}
};

pair<int, ll> dijkstra() {
	priority_queue<P> pq;
	vector<ll> dist(n + 1, 1e11);
	for (int i = 0; i < k; ++i) {
		pq.push({ K[i], 0 });
		dist[K[i]] = 0;
	}

	while (!pq.empty()) {
		P p = pq.top(); pq.pop();
		int cn = p.cn;
		ll cv = p.cv;
		if (dist[cn] < cv) continue;

		for (const Edge& next : edges[cn]) {
			int nn = next.nn;
			ll nv = next.nv;
			
			if (dist[nn] > cv + nv) {
				dist[nn] = cv + nv;
				pq.push({ nn, cv + nv });
			}
		}
	}
	auto it = max_element(dist.begin() + 1, dist.end());
	return { it - dist.begin(), *it };
}

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

	cin >> n >> m >> k;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges[b].push_back({ a, c });
	}

	for (int i = 0; i < k; ++i) cin >> K[i];
	auto res = dijkstra();
	cout << res.first << "\n" << res.second;
}
728x90