[BOJ][백준 1753] 최단경로 구하기 - C++

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

1753번: 최단경로

백준 사이트의 1753번 문제, 최단경로 구하기 문제다.

본인은 C++로 문제풀이를 진행하였다.

 

[BOJ][백준 1916] 최소비용 구하기 - C++

어제 업로드했던 위 문제를 풀고나서 Dijkstra 알고리즘에 대한 복습이 더 필요함이 느껴져서 고른 문제다.

---

0. 문제 읽기

문제의 입력과 출력

 

• 보통 최단경로를 구하는 문제는 BFS(너비 우선 탐색) 알고리즘으로 문제풀이를 하기 마련인데, 이 문제는 간선의 가중치가 주어져있어 Dijkstra 알고리즘을 사용하는 문제다.
• Dijkstra 알고리즘을 사용하여 주어진 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 문제

---

1. 문제풀이 아이디어

• 가중치가 있는 그래프에서 최소비용을 구하는 알고리즘인 Dijkstra의 기본 형식이다.
  • 참고1) 가중치가 없는 그래프의 최단경로 => BFS 알고리즘 (너비 우선 탐색 알고리즘)
  • 참고2) Dijkstra알고리즘은 가중치에 음수가 포함된 경우에는 사용할 수 없다!
• 단방향 그래프이다.
• Dijkstra 알고리즘 구현에는 for문을 사용하는 방법(시간복잡도: O(N^2))과 우선순위 큐를 사용하는 방법(시간복잡도: O(NlogN)) 두가지가 있다.
• 나는 그중에서 우선순위 큐를 사용한 방법으로 문제를 해결하였다.
• 백준 1916번 문제와의 차이점은 딱 경로값 하나를 출력하는지 전부를 출력하는지 차이이다. (그래서 왜 난이도 차이가 나는지 모르겠다)

---

2. 코드 핵심 부분

1) dijkstra 알고리즘 구현 함수,

   기본적인 틀 그대로 사용하여 특별한 점은 없다.

// 다익스트라 알고리즘 구현
void dijkstra(int start) {

	// 다익스트라 알고리즘을 위한 초기 세팅
	priority_queue<Edge> pq;
	for (int i = 1; i <= V; i++)
		dist[i] = Max;
	int visited[20001] = { 0 };

	pq.push({ start, 0 });
	dist[start] = 0;

	while (!pq.empty()) {
		Edge Now = pq.top();
		pq.pop();

		if (visited[Now.to])
			continue;
		visited[Now.to] = 1;

		for (int i = 0; i < al[Now.to].size(); i++) {
			Edge Next = al[Now.to][i];
			int ncost = Next.cost + Now.cost;
			if (ncost >= dist[Next.to])
				continue;

			dist[Next.to] = ncost;
			pq.push({ Next.to, ncost });
		}
	}
}

 

2) 정답을 출력하는 output 함수,

   만약 dist 값이 초기 세팅한 Max값 그대로면 경로가 존재하지 않는 경우이기 때문에 INF를 출력하고,

   dist값에 변화가 있으면 그 값을 출력해준다.

// 출력을 하는 함수
void output() {
	for (int i = 1; i <= V; i++) {
		if (dist[i] == Max)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}
}

---

3. 전체 코드

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

using namespace std;

#define Max 21e8

struct Edge {
	int to;
	int cost;

	// 비교 연산을 위한 연산자 오버로딩
	bool operator < (Edge Next) const {
		if (cost < Next.cost)
			return false;
		if (cost > Next.cost)
			return true;
		return false;
	}
};

// 필요한 전역 변수들
int V, E;  // 정점과 간선의 개수
vector<Edge> al[20001];  // 인접 리스트
int st;  // 시작 정점
int dist[20001];  // 최단 거리를 저장하는 배열

// 입력을 받는 함수
void input() {
	cin >> V >> E >> st;  // 정점의 개수, 간선의 개수, 시작 정점을 입력 받음
	int from, to, cost;
	for (int i = 0; i < E; i++) {
		cin >> from >> to >> cost;
		al[from].push_back({ to, cost });  // 간선을 인접 리스트에 추가함
	}
}

// 다익스트라 알고리즘 구현
void dijkstra(int start) {

	// 다익스트라 알고리즘을 위한 초기 세팅
	priority_queue<Edge> pq;
	for (int i = 1; i <= V; i++)
		dist[i] = Max;
	int visited[20001] = { 0 };

	pq.push({ start, 0 });
	dist[start] = 0;

	while (!pq.empty()) {
		Edge Now = pq.top();
		pq.pop();

		if (visited[Now.to])
			continue;
		visited[Now.to] = 1;

		for (int i = 0; i < al[Now.to].size(); i++) {
			Edge Next = al[Now.to][i];
			int ncost = Next.cost + Now.cost;
			if (ncost >= dist[Next.to])
				continue;

			dist[Next.to] = ncost;
			pq.push({ Next.to, ncost });
		}
	}
}

// 출력을 하는 함수
void output() {
	for (int i = 1; i <= V; i++) {
		if (dist[i] == Max)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}
}

// 메인 함수
int main() {

	// 입력
	input();

	// 다익스트라 알고리즘 수행
	dijkstra(st);

	// 출력
	output();

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과

하루전에 다익스트라 알고리즘이 생각나지 않아 당황하고

바로 복습을 위해 고른 문제다.

 

이번에는 잘 풀어낸 것 같아 만족스럽다.