[Baekjoon] 11403번: 경로 찾기

🥅 문제

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

 

🔍 설계

모든 i, j 쌍에 대하여 i에서 j로 이동할 수 있는지 묻고 있으므로, i에서 j까지 가는데 거리가 0보다 크기만 하면 된다. 모든 쌍에 대한 최단 거리를 구하는 플로이드 워셜 알고리즘을 이용하여 i와 j가 연결되어 있는지 확인할 때, 중간지점인 k를 설정하고, i와 k, k와 j가 연결되어 있으면 i와 j가 연결되어 있는 것으로 갱신한다. 

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, temp;
vector<vector<int>> adj_matrix(100, vector<int>(100));

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> adj_matrix[i][j];
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (adj_matrix[i][k] != 0 && adj_matrix[k][j] != 0) {
					adj_matrix[i][j] = 1;
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << adj_matrix[i][j] << " ";
		}
		cout << "\n";
	}
	
	return 0;
}