https://www.acmicpc.net/problem/11404
플로이드-워셜 알고리즘?
알고리즘 제목에서도 알 수 있다싶이 이 문제는 한 도시에서 다른 도시까지 필요한 비용의 최솟값을 구하는 알고리즘 문제이기 때문에 그래프에서 한 지점에서 다른 지점까지의 최솟값을 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 된다.
특징으로는 다익스트라 알고리즘에 비해 구현이 쉽고 삼중 반복문을 사용하기 때문에 O(V^3)의 시간 복잡도를 갖는다. 삼중 반복문을 돌때 가장 바같쪽에 있는 for문의 변수가 중간 지점(경유하는 애)여야 한다!!! 이 알고리즘의 작동 방식은 아래 블로그에서 잘 설명되어 있어 참고하면 좋을 듯 하다.
구현 특징!
가장 큰 특징으로는 배열의 초기값을 10,000,000으로 잡은 것이다. 초기값을 -1로 잡고 해도 되지만 이렇게 할 경우 반복문에서 따로 -1인 것을 확인해줘야하므로 코드가 복잡해질 수도 있다. 초기값을 10,000,000으로 잡은 이유는 한 도시에서 다른 도시까지의 최대비용이 100,000이고 한 도시에서 다른 도시까지 거쳐가는 가장 큰 경우의 수는 98개 도시를 거쳐가는 것이므로 넉넉잡아 100*100,000의 계산값으로 나온 것이다. 이렇게 할 경우에!
graph[i][k]=min(graph[i][k],graph[i][j]+graph[j][k]);
만으로 삼중 for문을 구현 가능하기 때문이다!
이렇게 할 경우 맨 마지막에 그래프를 한 번 돌면서 값이 10,000,000이라면 도시에서 도시로 갈 수 없는 경우의 수이므로 0으로 바꿔주었고 이렇게 하는 것이 비효율적이지 않는 이유는 이미 플로이드 알고리즘을 돌면서 O(V^3)만큼의 시간복잡도를 썼기 때문에 이를 확인하는 이중for문은 O(V^2)밖에 걸리지 않아 무시할만 하다.
한 가지 주의해야할 점은 a도시에서 a도시로의 필요한 비용의 최솟값은 0이므로 (1->4: 10, 4->1: 5 라고 해도 1->1에 필요한 최솟값은 15가 아닌 0이다) 출발지와 도착지가 같을 때는 continue를 써줬다.
소스코드
#include <iostream>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<map>
#include<set>
using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int graph[101][101];
void clear() //엄청 큰 값으로 초기화
{
for(int i=0;i<=101;i++)
{
for(int j=0;j<=101;j++)
{
graph[i][j]=10000000;
}
}
}
int main() {
int city,bus;
cin>>city>>bus;
clear();
for(int i=1;i<=bus;i++)
{
int tmp1,tmp2,price;
cin>>tmp1>>tmp2>>price;
graph[tmp1][tmp2]=min(graph[tmp1][tmp2],price);
}
for(int j=1;j<=city;j++)
{
for(int i=1;i<=city;i++)
{
for(int k=1;k<=city;k++)
{
if(k==i) //a도시에서 a도시로의 비용은 0임
continue;
graph[i][k]=min(graph[i][k],graph[i][j]+graph[j][k]);
}
}
}
for(int j=1;j<=city;j++)
{
for(int i=1;i<=city;i++)
{
if(graph[j][i]==10000000) //한번도 방문하지 않은 곳
graph[j][i]=0;
cout<<graph[j][i]<<" ";
}
cout<<"\n";
}
}
'알고리즘! > Graph' 카테고리의 다른 글
[C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!) (1) | 2023.09.13 |
---|---|
[C/C++] 13549: 숨바꼭질 3 (BFS,Queue) (0) | 2023.09.12 |
[C/C++] 17070: 파이프 옮기기 1 (0) | 2023.08.29 |
[C] 1697: 숨바꼭질 (0) | 2023.08.23 |
[C] 11403: 경로 찾기 (0) | 2023.08.23 |