[S1] 백준 1446번 지름길 C++ 다익스트라, 최단 경로

리뷰

 

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

1D 최단 경로 문제, 알고리즘 분류에 DP가 있긴 한데, 다익스트라를 통해 문제를 풀이하였다.

 

전역 변수

• n, d : 주어지는 지름길의 개수 n, 목적지 까지의 거리 d
• Pos : 다익스트라를 진행할 때 직선 상에서의 현재 위치를 나타낼 구조체, 시간을 기준으로 오름차순 정렬한다.
• lst : 지름길 정보를 저장하기 위한 pair<int, int> 타입의 벡터, 최대 10001크기로 설정한ㄷ.

 

함수

1. dijkstra

int dijkstra()

 

다익스트라를 통해 목표 지점까지의 최단 경로를 구하는 함수

1. 정수형 벡터 dist를 d + 1 크기, 적당히 큰 값으로 초기화 한다, 나는 20억으로 세팅했다.
2. 시작 지점인 0을 dist[0] = 0을 통해 거리를 0으로 만들어 준다.
3. Pos타입의 우선 순위 큐 pq를 초기화 해주고, 시작 지점 0, 0을 push해준다.
4. pq가 빌때까지 반복문을 수행하고, 각 단계마다 현재 위치와 시간을 cx, ct로 초기화 해준다.
5. 만약 ct가 dist[cx]보다 크다면 아직 최신화 되지 않은 위치이니 더 탐색해줄 필요가 없다.
6. 먼저 lst[cx]가 empty가 아니라면 지름길이 존재하는 것이니 각 지름길을 갈 수 있는지 체크해 준다.
7. 만약 유효한 지름길이라면 이동 후 pq에 push를 진행해 준다.
8. 이후 지름길을 이용하지 않고 걸어가는 것이 빠를 수도 있으니 다음 위치로의 이동을 구현해 준다.
9. 모든 탐색을 마친 후 dist벡터의 d번째 인덱스를 리턴해 준다.

 

문제풀이

1. n, d값을 입력 받고, n개의 지름길을 입력 받아 lst벡터에 추가해 준다.
2. dijkstra함수를 실행하고 리턴 값을 출력해 준다.

 

참고 사항

시작 지점이 같은 지름길이 여러개 주어질 수 있으므로 vector를 사용해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#define pii pair<int, int>
using namespace std;

int n, d;

struct Pos {
	int x, t;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};
vector<pii> lst[10001];

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, ct = pos.t;
		if (ct > dist[cx]) continue;
		
		if (!lst[cx].empty()) {
			for (pii i : lst[cx]) {
				int nx = i.first, w = i.second;
				if (nx <= d && dist[nx] > ct + w) {
					dist[nx] = ct + w;
					pq.push({ nx, ct + w });
				}
			}
			
		}

		if (cx + 1 <= d && dist[cx + 1] > ct + 1) {
			dist[cx + 1] = ct + 1;
			pq.push({ cx + 1, dist[cx + 1] });
		}
	}
	return dist[d];
}

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

	cin >> n >> d;
	for (int i = 0; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		lst[a].push_back({ b, c });
	}

	cout << dijkstra();
}