백준 11403번 : 경로 찾기

문제 링크 : www.acmicpc.net/problem/11403

내 풀이(2021.1.27.) :

#include <iostream>
#include <limits.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V 100 // 노드 개수의 최대값

int V; // V : 노드의 개수
vector<vector<int>> VV_info(MAX_V + 1, vector<int>(MAX_V + 1, INT_MAX)); // 모든 노드에서 모든 노드까지의 최단 거리

void floyd_warshall() { // 플로이드 워셜
	// 점화식 수행
	for (int k = 1; k <= V; k++) {
		for (int a = 1; a <= V; a++) {
			for (int b = 1; b <= V; b++) {
				if (VV_info[a][k] != INT_MAX && VV_info[k][b] != INT_MAX) {
					VV_info[a][b] = min(VV_info[a][b], VV_info[a][k] + VV_info[k][b]);
				}
			}
		}
	}
}

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

	cin >> V;
	// 노드/간선 정보 초기화
	for (int a = 1; a <= V; a++) {
		for (int b = 1; b <= V; b++) {
			int c; cin >> c;
			if (c != 0) VV_info[a][b] = c;
		}
	}

	floyd_warshall();

	for (int a = 1; a <= V; a++) {
		for (int b = 1; b <= V; b++) {
			cout << (VV_info[a][b] == INT_MAX ? 0 : 1) << " ";
		}
		cout << endl;
	}

	return 0;
}

 

- V x V 크기의 인접 행렬을 가지고 플로이드 워셜을 수행하면 V x V 크기의 최단거리 행렬이 나온다.
- 기본적으로 인접 행렬의 대부분의 값은 INT_MAX로 초기화하지만, (i, i) 위치에 있는 대각선 값들은 경우에 따라 0으로 초기화할 수도 있고 INT_MAX로 초기화할 수도 있다.

1) 자기 자신에게 돌아올 수 없는 경우
- 인접 행렬의 대각선 값들을 0으로 초기화한다.
- 플로이드 워셜 수행 후, 최단거리 행렬의 대각선 값들이 무조건 0으로 나온다.

2) 자기 자신에게 돌아올 수 있는 경우
- 인접 행렬의 대각선 값들을 INT_MAX로 초기화한다.
- 플로이드 워셜 수행 후, 최단거리 행렬의 대각선 값들이 INT_MAX로 유지되거나 INT_MAX가 아닌 다른 값으로 갱신된다. (INT_MAX로 유지되면 자기 자신으로 돌아오는 경로가 없다는 뜻)

 

- 이 문제에서는 INT_MAX를 0으로 표현하기로 약속했으므로, 이에 대한 변환 처리만 해주면 된다.