https://school.programmers.co.kr/learn/courses/30/lessons/72413
특정 정점에서 나머지 정점에 대한 최소비용을 구하는 알고리즘으로는 다익스트라 , 벨만포드 알고리즘 등이 있지만 이 문제에서는 모든 정점간의 최소비용을 구해야 한다.
이 문제 에서는 플로이드 워샬(Floyd-Warshall) 알고리즘을 통해서 구현해 주었다.
다익스트라 알고리즘 동작원리
지금부터 '비용' 이라는 말을 많이 사용하게 될 텐데, 이 값은 1차원 배열 Dist[] 라는 배열에 저장되어 있다고 생각하자.
초기 Dist배열의 모든 값은 무한대(INF)로 초기화 되어 있다.
다익스트라 알고리즘의 동작 원리를 순서대로 적어보자면 다음과 같이 작동한다.
-
시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로
체크한다.
-
방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로
선택해준다.
-
2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.
-
2 ~ 3번 과정을 반복한다.
다익스트라 알고리즘 구현
- 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.
for (int i = 1; i <= V; i++) Dist[i] = MAP[Start][i];
Dist[Start] = 0;
Select[Start] = true;
- 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로
선택해준다.
int Find_Shortest_Node()
{
int Min_Dist, Min_Idx;
Min_Dist = INF;
Min_Idx = -1;
for (int i = 1; i <= V; i++)
{
if (Select[i] == true) continue;
if (Dist[i] < Min_Dist)
{
Min_Dist = Dist[i];
Min_Idx = i;
}
}
return Min_Idx;
}
- 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.
void Update_Dist(int NewNode)
{
for (int i = 1; i <= V; i++)
{
if (Select[i] == true) continue;
if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
{
Dist[i] = Dist[NewNode] + MAP[NewNode][i];
}
}
}- 2 ~ 3번 과정을 반복한다. (n-1 번 반복)
플로이드 워샬 동작원리
플로이드 와샬 알고리즘의 동작 원리는 매우 간단하다. 정점
i 와 j의 최단 거리를 계산할 때, 모든 정점 k에 대해 i→k→j가 i→j보다 짧다면 k를 경유하는 것으로 최단 거리를 바꾸어 주면 된다.
플로이드 워샬 구현
for (int 중간점 = 1; 중간점 <= N; 중간점++)
{
for (int 시작점 = 1; 시작점 <= N; 시작점++)
{
for (int 도착점 = 1; 도착점 <= N; 도착점++)
{
if : Dist[시작점][중간점] + Dist[중간점][도착점] < Dist[시작점][도착점]
=> Dist[시작점][도착점] = Dist[시작점][중간점] + Dist[중간점][도착점]
}
}
}프로그래머스 정답
#include <string>
#include <vector>
#define INF 987654321
using namespace std;
int Min(int A, int B) { if (A < B) return A; return B; }
void Make_Distance(vector<vector<int>> fares, vector<vector<int>> &Dist, int n)
{
for (int i = 0; i < fares.size(); i++)
{
int S = fares[i][0];
int E = fares[i][1];
int D = fares[i][2];
Dist[S][E] = D;
Dist[E][S] = D;
}
for (int i = 1; i <= n; i++) Dist[i][i] = 0;
}
void Floyd_Warshall(int n, vector<vector<int>> &Dist)
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j || i == k || k == j) continue;
if(Dist[i][k] != INF && Dist[k][j] != INF) Dist[i][j] = Min(Dist[i][j], Dist[i][k] + Dist[k][j]);
}
}
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares)
{
int answer = 0;
vector<vector<int>> Dist(n + 1, vector<int>(n + 1, INF));
Make_Distance(fares, Dist, n);
Floyd_Warshall(n, Dist);
answer = Dist[s][a] + Dist[s][b];
for (int i = 1; i <= n; i++)
{
if (Dist[s][i] != INF && Dist[i][a] != INF && Dist[i][b] != INF)
{
answer = Min(answer, Dist[s][i] + Dist[i][a] + Dist[i][b]);
}
}
return answer;
}
https://yabmoons.tistory.com/622 //플로이드워샬
https://yabmoons.tistory.com/364 //다익스트라
U+221E