백준 1719(택배)

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

1719번: 택배

N개의 점이 있을 때, 각각의 점에서 나머지 점까지 최단 경로로 이동할 때, 가장 먼저 거쳐가야 하는 점을 찾는 문제이다.

 

N개의 점에서 나머지 N개의 점까지의 최단 거리를 구하는 문제 => 플로이드 와샬

 

O(N^3) 200^3  = 8*10^6이므로 시간복잡도에서 문제가 되지 않는다.

 

 

그럼 이제 최단경로로 이동한다고 했을 때, 가장 먼저 들려야 하는 지점을 찾는게 문제인데 플로이드 와샬의 작동원리를 잘 파악해보자 

 

플로이드 와샬은 A에서 B로 이동한다고 했을 때, C지점을 거쳐서 가는 경우, D,E,F... 등 나머지 지점을 거쳐서 가는 경우 중 더 최단 경로가 있으면 그 경로로 최신화해준다. 

 

핵심은 더 최단경로가 있으면 최신화

 

따라서 더 최단경로로 최신화 할때에 찾으려는 정답도 찾을 수 있다. 

 

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (garb[j][k] > garb[j][i] + garb[i][k]) {
					garb[j][k] = garb[j][i] + garb[i][k];
					answer[j][k] = i;
				}
			}
		}
	}

 

 

 

처음에는 answer[j][k] = i로 해서 1->6으로 가야하는 경우에 5를 거쳐서 가는게 더 작으면 answer[1][6] = 5를 저장했었다.

 

하지만 원하는 결과를 얻기 위해서는 answer[1][5] 도 확인, 만약 answer[1][5] = a (a != 5) 라면 answer[1][a] 도 확인 해야했다. 그래서 따로 재귀함수를 만들어서 원하는 root값을 찾으려 했지만 결과는 런타임에러

 

아마도 재귀함수의 깊이가 깊어져서 그랬던 것 같다. 

 

그래서 코드를 수정 원하는 결과를 얻을 수 있었다. 

 

answer[j][k] = answer[j][i];

 

#include<iostream>
using namespace std;
#define MAX 201

int N, M, a, b, c, INF = 987654321;
int garb[MAX][MAX];
int answer[MAX][MAX] = { 0 };


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		garb[a][b] = c;
		garb[b][a] = c;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			if (garb[i][j] == 0)
				garb[i][j] = INF;
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (garb[i][j] != 0 && garb[i][j] != INF)
				answer[i][j] = j;
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (garb[j][k] > garb[j][i] + garb[i][k]) {
					garb[j][k] = garb[j][i] + garb[i][k];
					answer[j][k] = answer[j][i];
				}
			}
		}
	}


	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) cout << "- ";
			else cout << answer[i][j] << " ";
		}
		cout << "\n";
	}
}

 

 

어디에나 쓰일 수 있는 테크닉들을 기억해두자