대엉코딩

www.acmicpc.net/problem/11404

1. 풀이방법

- 문제를 읽다보면 문제에서는 버스, 즉 간선(단방향)이 비용(가중치)를 각각 가지고 있다.

- (->BFS로는 구할 수 없겠구나 ! 라는 생각)

- 다익스트라 또는 플로이드 워셜 (대표적)

- 근데 출력을 보니 모든 도시에서 자신을 제외한 모든 점까지의 최단거리를 출력하는 문제 (자신 또는 못가는 경우 0 )

- (-> 플로이드 워셜 ! )

2. 주의사항

- 구현 시 도시사이의 거리를 입력 받기전 가장 큰 값으로 초기화 해줘야 하는데 COST가 100,000을 넘지 않는 다는 말을

- 보고 100001으로 정의해두었다가(INF) 계쏙 98퍼에서 오류가 뜨길래...생각해보니...

- 거쳐서 가는경우 100,000을 그냥 넘을 수 있다는 것......!!! 주의주의.... 그래서 그냥 987654321로 초기화 하였다

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 987654321

int n, m;
int CityToCity[101][101];

void inputs() { //입력함수
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) { //초기화
			if (i == j) continue;
			CityToCity[i][j]=INF;
		}
	}
	int start, end, cost;
	for (int i = 0; i < m; i++) {
		cin >> start >> end >> cost;
		if (CityToCity[start][end] > cost) {
			CityToCity[start][end] = cost;
		}
	}
}

void Searchmin() {
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= n; b++) {
			for (int c = 1; c <= n; c++) {
				if (CityToCity[b][a] != INF && CityToCity[a][c] != INF) { //거쳐서 갈 수 있는 경우
					CityToCity[b][c] = min(CityToCity[b][c], (CityToCity[b][a] + CityToCity[a][c]));
				}
			}
		}
	}
}
void outputs() { //출력함수
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (CityToCity[i][j] == INF||i==j)  cout << 0 << " "; 
			else cout << CityToCity[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	inputs();
	Searchmin();
	outputs();
	return 0;
}

0.Transitive Closure

- 그래프 G가 주어졌을 떄 G*은 G와 같은 정점집합(same vertices)을 가진다.

- 만약 그래프 G가 정점 u에서 v로 경로를 가지면 그래프 G*는 정점 u에서 v로 간선(edge)를 가진다.

- Transitive Closure은 경로가 존재하는 지 여부를 알 수 있다.

- 물론 모든 정점에서 DFS를 수행하면 O(n(n+m)) --링크드리스트로 구현되어있다면

  에 알아낼 수 있다.

1. 개요

- 플로이드 워셜 알고리즘은 그래프에서 Transitive Closure을 구하거나

  n:n(다대다) shortest path를 구하는 데 사용 된다.

- Dynamic Programming 알고리즘이다.

- "A에서 B로 갈 수 있고 B에서 C로 갈 수 있는데 AC간선이 없다면, 간선을 연결해준다."

2.아이디어

- 모든 정점들을 번호로 관리한다.

- n단계로 구성되어 차례차례 확장해나가는 구조.

- k번째 단계의 수행이 완료되면, 1~k까지의 간선들은 모두 활용한 것 이다.

- 친구들끼리 연락을 해야하는 상황을 생각해보면 이해가 쉽다.

   (난 A의 전화번호를 모르지만 B의 번호를 알고있다. B는C의 번호를알고있다.

     그럼 난 두 단계를 거치면 C의 번호를 알게된다.)

3.The Floyd-Warshall Algorithm(플로이드 워셜 알고리즘)

- 각 단계의 그래프를 G0,G1,.......Gn이라 하자.

- 정점들은 v1,v2,.....,vn이라 한다.

- k단계에서 Gk는 Gk-1으로 부터 계산한다.

- 수행시에 adjacent연산을 많이 쓰는데 (두 정점 사이에 경로가 있는지 u->v)

   그럼 Graph를 구현 할 때 인접행렬로 구현하는 게 좋겠죠~

- 전화번호 예시에 빗대어 설명하였습니다.

-그럼 n:n shortes path는 어떻게 구하느냐??
- 기본적인 원리는 위와 같습니다만, 새로 알게된 경로가 기존의 경로보다 짧을 경우에 그 값을 넣어주고

   그렇지 않은 경우는 update하지 않습니다.

- 처음 초기화를 무한대로 해줍니다.

4.Example

(1)

(2)

(3)

(4)

(5)

5. 분석(Analysis)

- n:n shortest path를 구할 때 n번의 다익스트라 알고리즘을 호출하면 O(nmlogn)의 시간 복잡도를 가진다.

- 플로이드 워셜 알고리즘은 O(n*3)의 시간 복잡도를 가진다.