백준 11780(플로이드 2)

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

11780번: 플로이드 2

 

 

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

11404번: 플로이드

 

이 문제에서 훨씬 더 어려운 조건이 추가되었는데, 난이도는 같다? ㅋㅋㅋ 

어이가 없음. 난이도 책정방식이 너무 잘못된것같다. 그냥 알고리즘별로 난이도를 책정해놓고 그것대로만 하는 느낌? 

 

N개의 지점에서 N개의 각자 다른 지점까지의 최단거리를 구하는 문제이다. 

 

딱봐도 플로이드 와샬을 사용하는 문제인 것 같다. 

11404 플로이드 문제는 플로이드 와샬 개념을 한번만 사용하면 끝나는 문제이고, 

 

11780 플로이드 2 문제는 여기에 어떤 경로를 통해서 가야지 최단 거리로 갈 수 있을까를 묻는 문제이다. 

 

이 문제를 풀 때에 여기에 초점을 맞춰서 생각을 했고, 

 

1->5까지의 최단거리를 조사할때

 

만약 그 경로가 1->3->2->5 라고 한다면 

 

분명 3->2->5 로 갱신 된 다음에 

 

1->3->2

1->3->5과 같은 방식으로 갱신 되었을 것이다.

 

왜냐하면 플로이드 와샬은 1에서 n까지의 오름차순 순서로 거치는 점을 조사하기 때문에 

 

거쳐가는 점이 2인 경우, 3인 경우 순서로 조사했을 것이다. 

 

따라서 3->5로 갈때 거치는 점을 저장했다. 

 

parent[3][5] = 2;

 

그 뒤에 구조를 확인해보면 

 

트리구조랑 같은 것을 알 수 있었다. 

 

     

   3  

1    2 

       5

 

만약 위의 가정대로 갱신이 되었다고 하면 3이 root노드가 되고 이 것을 중위 순회하면 1->5까지 가는 경로를 알 수 있다. 

 

void solve(int l, int r, int root) {
	if (root == 0) return;
	solve(l, root, parent[l][root]);
	q.push(root);
	cnt++;
	solve(root, r, parent[root][r]);
}

 

중위순회 함수이다. cnt는 solve함수 호출시마다 초기화했다. 

 

그리고 위 함수의 경우 최초의 l과 r은 q에 넣지 않는다. 그래서 따로 넣어주었다.

#include<iostream>
#include<queue>
using namespace std;
#define MAX 101

int n, m, a, b, c, INF = 987654321, cnt;
int city[MAX][MAX];
int parent[MAX][MAX];
queue<int> q;

void solve(int l, int r, int root) {
	if (root == 0) return;
	solve(l, root, parent[l][root]);
	q.push(root);
	cnt++;
	solve(root, r, parent[root][r]);
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			city[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		if (city[a][b] > c)
			city[a][b] = c;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (city[i][j] > city[i][k] + city[k][j]) {
					city[i][j] = city[i][k] + city[k][j];
					parent[i][j] = k;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (city[i][j] == INF) cout << "0 ";
			else cout << city[i][j] << " ";
		}
		cout << "\n";
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (city[i][j] == 0 || city[i][j] == INF) {
				cout << "0\n";
			}
			else {
				if (parent[i][j] == 0) {
					cout << "2 " << i << " " << j << "\n";
				}
				else {
					cnt = 0;
					q.push(i);
					solve(i, j, parent[i][j]);
					q.push(j);
					cout << cnt + 2 << " ";
					while (!q.empty()) {
						cout << q.front() << " ";
						q.pop();
					}
					cout << "\n";
				}
			}
		}
	}
}

 

O(n^3) or O(n^2 * 재귀함수)라서 걱정을 많이 한 문제지만 테스트케이스에 그런경우는 존재하지 않는 것 같다. 아직까지 재귀함수의 시간복잡도를 잘 모르겠는데, 많이 틀려보면서 배우지 않을까 생각한다.