![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
전형적인 플로이드 워셜 알고리즘 문제이다.
n개의 도시중 두 도시를 지나는 버스들이 있고, 버스마다 비용이 다른 상황에서
도시와 도시를 지나는 최단 비용을 구하는 문제이다.
이런 최단 비용을 탐색하는 알고리즘은 대표적으로 플로이드 워셜, 다익스트라가 있다. 플로이드 워셜은 모든 지점에서 모든 지점으로의 최소 비용을 모두 구할 수 있지만, 다익스트라는 하나의 시작 지점에서 부터 모든 지점으로의 최소 비용을 계산할 수 있다.
다만, 플로이드 워셜은 O(n^3)이라는 무지막지한 시간복잡도를 보유하고 있기 때문에 노드의 수가 약 400개 이하일 때만 사용할 수 있다고 생각하면 된다.
먼저 입력과 초기화에 대한 코드이다.
int NumOfCity = 0;
int NumOfBus = 0;
std::cin >> NumOfCity >> NumOfBus;
std::vector<std::vector<int>> Cost(NumOfCity, std::vector<int>(NumOfCity, 50000000));
for (int i = 0; i < NumOfBus; i++)
{
int Start = 0;
int End = 0;
int BusCost = 0;
std::cin >> Start >> End >> BusCost;
Cost[Start - 1][End - 1] = std::min(Cost[Start - 1][End - 1], BusCost);
}
for (int i = 0; i < NumOfCity; i++)
{
Cost[i][i] = 0;
}
도시의 수와 버스의 수를 먼저 입력받은 뒤, 도시의 수를 높이, 너비로 가진 이차원 벡터를 구성해주었다.
연결되지 않은 도시를 표현하기 위해 50000000이라는 큰 숫자로 먼저 벡터의 원소들을 초기화 하였다.
이후, 버스의 정보를 입력받았다.
어디서 시작되어 어디까지 가는지, 비용은 얼마인지 3가지 정보가 입력된다.
동일한 구간이 다른 비용으로 여러 번 입력될 수도 있기 때문에, Cost[Start - 1][End - 1] 은 기존의 값과 새로 입력되는 값중 최소값으로 설정해주었다.
입력을 모두 받은 이후, i와 j가 같은 지점의 Cost는 모두 0으로 설정해주었다.
(시작지점과 도착지점이 같다면, 비용이 들지 않기 때문이다.)
for (int i = 0; i < NumOfCity; i++)
{
for (int j = 0; j < NumOfCity; j++)
{
for (int k = 0; k < NumOfCity; k++)
{
Cost[j][k] = std::min(Cost[j][k], Cost[j][i] + Cost[i][k]);
}
}
}
이후, 무식하게 3중 반복문을 돌리면 이게 플로이드 워셜 알고리즘 끝이다.
j -> k로 가는 비용과 j -> i -> k 처럼 i를 거쳐가는 비용중 더 저렴한 값으로 Cost를 갱신하는 과정을
모든 지점에 대해서 반복하면 된다.
반복문이 모두 끝나고 나면, 배열의 모든 값은 최소값으로 갱신되어 있을 것이며, 이동할 수 없는 지점의 값은 최초에 초기값으로 설정해둔 50000000이 들어있을 것이다.
for (int i = 0; i < NumOfCity; i++)
{
for (int j = 0; j < NumOfCity; j++)
{
if (Cost[i][j] == 50000000)
{
Cost[i][j] = 0;
}
std::cout << Cost[i][j] << " ";
}
std::cout << "\n";
}
이후 출력하면 된다. 다만, 문제의 경우엔 도착할 수 없는 지점은 0으로 표기하라고 되어있기 때문에
값이 50000000인 지점은 모두 0으로 변경해준 뒤에 출력해야 한다.
![](http://t1.daumcdn.net/tistory_admin/static/images/xBoxReplace_250.png)
알고리즘이 명확한 문제인 만큼, 대부분 속력과 메모리 사용량이 고만고만 하게 나온다.
플로이드 워셜이라는 알고리즘을 알고 있다면 상당히 간단하게 풀리는 문제이다.
그렇기 때문에 간단한 문제에서 헤메지 않으려면 알고리즘에 대한 지식은 꾸준히 늘리는 것이 좋을 것 같다.
'코딩테스트 문제 풀이 (C++)' 카테고리의 다른 글
백준 1890 - 점프 (C++) (0) | 2024.04.02 |
---|---|
프로그래머스 - 2 x n 타일링 (C++) (1) | 2024.04.01 |
프로그래머스 - 피로도 (C++) (0) | 2024.04.01 |
백준 11501 - 주식 (C++) (1) | 2024.03.31 |
백준 1158 - 요세푸스 문제 (C++) (0) | 2024.03.30 |