백준 11404 c++ "플로이드" -PlusUltraCode-

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

 

 

 

 

[필자 사고]

1. 모든 경로의 최단 경로를 요구하는 문제이다.

2. 특정한 시작점이 아니다. (다익스트라 x 벨만포드 x )

플로이드 와샬 알고리즘을 이용하면 쉽게 해결할 수 있따.

이 문제에서 조심해야 되는건 버스노선 입력할 때 똑같은 경로가 다른 가중치로 적힐 수 있따. 

그래서 필자는 if(arr[s][e]>w) 일 경우 값을 갱신해주는 방법으로 함정을 피해갔다.

 

아래는 소스코드 해설이다.

 

 

Input() 함수는 첫 번째로 사용자로부터 노드의 수 N과 간선의 수 M을 입력받는다.
이후, 2차원 배열 arr을 노드의 수에 맞게 초기화하는데, 각 배열의 값은 초기값으로 매우 큰 값인 999999999로 설정된다.
이는 도달 불가능한 경로를 나타내기 위한 값이다. 자기 자신으로 가는 경로는 존재하므로 각 노드에서 자신으로의 경로(arr[i][i])는 0으로 설정된다.
그런 다음, 사용자로부터 각 간선의 시작점, 끝점, 가중치를 입력받고, 해당 가중치가 더 작으면 배열에 저장한다.

Floid_WarShall() 함수는 플로이드-와샬 알고리즘을 사용하여 모든 노드 간의 최단 경로를 계산한다.

삼중 반복문을 통해 모든 노드 쌍에 대해 중간 노드를 거쳐가는 경로가 더 짧은지 확인하고, 더 짧으면 배열 값을 갱신한다. 이를 통해 모든 노드 간의 최단 경로가 구해진다.

 

 

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<vector<long>> arr;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		arr[i].resize(N + 1,999999999);

		
	}

	for (int i = 0; i <= N; i++) {
		arr[i][i] = 0;
	}

	for (int i = 0; i < M; i++) {
		int s, e;
		long w;
		cin >> s >> e >> w;
		if(arr[s][e]>w)arr[s][e] = w;
	}
}

void Floid_WarShall() {
	
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (arr[s][e] > arr[s][k] + arr[k][e]) {
					arr[s][e] = arr[s][k] + arr[k][e];
				}
			}
		}
	}
}


void Print() {
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			if (arr[i][k] == 999999999) {
				cout << 0 << " ";
				continue;
			}
			cout << arr[i][k] << " ";
		}
		cout << '\n';
	}
}

void GameStart() {
	Floid_WarShall();
	Print();
}

int main(void) {
	Input();
	GameStart();
}