[알고리즘][C++] Dijkstra (다익스트라) / 최단 경로 탐색

백준 5972 : 택배 배송

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

5972번: 택배 배송

 

 

접근 방향 및 디버깅

[1] 최초 접근

- N * N 배열을 만들어 정점별로 연결된 정점과의 거리를 표시하고, 이후 우선순위큐와 Visited 배열을 사용해 탐색을 진행하고자 함

- 해당 접근으로 TC 답은 나왔으나, 메모리가 128 MB 로 제한되어 있어서 약 3% 대부터 메모리 터짐

- 당연함.. N 의 최대값이 50000 이라는 점을 제대로 확인하지 않음 

 

[2] 수정된 접근

- 똑같이 2차원 배열을 만들되, N * N 이 아닌 N * n (해당 정점과 연결된 정점의 수) 로 수정 

- 각 정점을 돌면서 연결된 모든 정점을 확인하는 방식으로 진행 

- 성공

 

코드

/*
	1, 2, 3 차: 컴파일 에러 (limits 대신 climits 사용하니 ok)
	4차:		메모리 에러 (3%) -> INT_MAX 제거
	5차:		메모리 에러 (3%) -> priority queue 제거 
	6차:		메모리 에러 (3%) -> 2차원 배열이 문제인 걸 깨닫고 로직 수정
	7차:		성공!! (5240KB, 88ms)			 
*/

/* 7차 시도 */
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>

using namespace std;
int main() {

	freopen("input.txt", "r", stdin);
	
	int N, M;
	cin >> N >> M;

	vector<vector<pair<int, int>>> arr(N + 1);
	
	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		arr[A].push_back(make_pair(B, C));
		arr[B].push_back(make_pair(A, C));
	}

	vector<int> res(N + 1, INT_MAX);
	priority_queue<pair<int, int>> q;

	q.push(make_pair(0, 1));
	res[1] = 0;

	while (!q.empty()) {

		pair<int, int> tmp = q.top(); q.pop();
		int cur = tmp.second;
		int dist = tmp.first;

		for (int i = 0; i < arr[cur].size(); i++) {
			int nextNode = arr[cur][i].first;
			int nextDist = arr[cur][i].second;
			if (res[cur] + nextDist < res[nextNode]) {
				res[nextNode] = res[cur] + nextDist;
				q.push(make_pair(nextDist * -1, nextNode));
			}
		}

	}

	cout << res[N];

	return 0;
}

/* 4차 시도
#include <stdio.h>
#include <queue>
#include <vector>
#include <iostream>
#include <climits> // INT_MAX
#include <utility>

using namespace std;

int main() {

	//freopen("input.txt", "r", stdin);

	int N, M;
	cin >> N >> M;

	vector<vector<int>> arr(N + 1);
	for (int i = 1; i <= N; i++) {
		arr[i].resize(N + 1, -1);
	}

	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		arr[A][B] = C;
		arr[B][A] = C;
	}

	vector<int> res(N + 1, INT_MAX);
	vector<int> V(N + 1, 0);
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0, 1));

	while (!q.empty()) {

		pair<int, int> cur = q.top(); q.pop();
		int dist = cur.first * -1;
		int node = cur.second;
		V[node] = 1;

		for (int i = 1; i <= N; i++) {
			if (V[i]) continue;
			if (arr[node][i] == -1) continue;

			int minDist = res[i];
			int curDist = dist + arr[node][i];

			if (curDist < minDist) {
				res[i] = curDist;
				q.push(make_pair(-curDist, i));
			}
		}

	}

	cout << res[N];

	return 0;
}
*/

 

배운 점

- 문제 풀이 전에 시간 복잡도, 공간 복잡도를 정확히 잘 계산해보자.. 나 이제 파이썬 안 쓴다 C++ 쓴다