[ 백준 11404 ] 플로이드 (C++)

 

 

11404번: 플로이드

 

 

문제!

---

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

---

설명이 간단한 문제... 이해하는데는 어려운 점이 없어보입니다!

 

 

그럼 어떻게 풀어나가야할까요..

 

일단 구해야하는건 

각 지점에서 다른 지점으로 가는 최단경로를 구해야하는데

map[0][5] = 0에서 5까지 가는데 최단거리! 를 모두 구해 주어야합니다.

 

 

지금 까지 사용했던 알고리즘을 생각해보면

1. dfs bfs >>> 경로가 필요할때 , 트리일 경우

2. 다익스트라 >> 한 지점에서 다른 모든 지점의 최단경로

 

이번엔 모든 지점을 구해 주어야하는데 다익스트라를 도시만큼 돌려주기에는 도시 n=100

무리가 있어 보입니다. 

 

 

그렇기에 이번에 새로 사용해볼 알고리즘은 문제이름과 같은 플로이드 워샬 알고리즘!

 

 

플로이드 워샬

---

출발지와 도착지, 그리고 경유지를 통해 모든 지점의 최단거리를 구하는 알고리즘으로 구조는

 

 

아래처럼 간단합니다.

    for (int k = 1; k <= n; k++) {//중간 경유지
		for (int i = 1; i <= n; i++) { // 시작
			for (int j = 1; j <= n; j++) {// 끝
				bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j]);
			}
		}
	}

i 에서 j까지의 거리를  i 에서 k  +  k에서 j  로 나누어 최단거리를 계산한다고 생각하시면 될 것 같습니다!

 

 

그럼 바로

 

코드!

---

선언부에서는 다음과 같이 추가해 줍시다.

long long n, m, a, b, c;// 도시수 버스수 시작 도착 비용

vector<vector<long long>> bus(1000001);

vector <long long> allMap;

 

그리고 모든 버스에 대해 값을 초기화 해줍시다.

for (int i = 0; i < n + 1; i++) {
		bus[i].resize(n + 1, 987654321);
}

 

 

다음은 입력부.. 여기서 같은 지역으로 이동하는 버스가 중복으로 존재할 수 도 있기에 min으로 처리 해주어야합니다.

(당했네요)

for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		bus[a][b] = min(bus[a][b],c);// 도착 비용
		
	}

 

 

다음은 모든 장소에 대해 플로이드 워샬 알고리즘으로 최단거리를 구해줍시다.

allMap.resize(n + 1, 0);


	for (int k = 1; k <= n; k++) {//중간
		for (int i = 1; i <= n; i++) { // 시작
			for (int j = 1; j <= n; j++) {// 끝
				if (i == j) {
					bus[i][j] = 0;
				}
				bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j]);
			}
		}
	}

 

 

출력부분에서 갈 수 없는 지역을 따로 처리해주고 나머지는 그대로 출력해줍시다.

for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (bus[i][j] == 987654321) {
				cout << 0<<" ";
			}
			else {
				cout << bus[i][j] << " ";
			}
		}
		cout << endl;	
	}

 

 

여기까지가 끝!

 

 

 

 

 

이번 문제를 통해 배운 내용

1. 모든지역에서의 최단거리를 구할시엔 플로이드워샬 알고리즘

2. 입력에 대해 좀 더 깊이 생각 

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>

using namespace std;


long long n, m, a, b, c;// 도시수 버스수 시작 도착 비용



vector<vector<long long>> bus(1000001);

vector <long long> allMap;


int main() {

	cin >> n >> m;


	for (int i = 0; i < n + 1; i++) {
		bus[i].resize(n + 1, 987654321);
	}


	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		bus[a][b] = min(bus[a][b],c);// 도착 비용
		
	}

	allMap.resize(n + 1, 0);


	for (int k = 1; k <= n; k++) {//중간
		for (int i = 1; i <= n; i++) { // 시작
			for (int j = 1; j <= n; j++) {// 끝
				if (i == j) {
					bus[i][j] = 0;
				}
				bus[i][j] = min(bus[i][j], bus[i][k] + bus[k][j]);
			}
		}
	}
	


	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (bus[i][j] == 987654321) {
				cout << 0<<" ";
			}
			else {
				cout << bus[i][j] << " ";
			}
		}
		cout << endl;	
	}
	


	return 0;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!