백준 11403. 경로 찾기(C++)

11403.경로 찾기

11403번: 경로 찾기

---

입력

• 첫째 줄에 정점의 개수 N이 주어진다.
• 둘째 줄부터 N개 줄에 그래프의 인접 행렬이 주어진다.

---

문제 풀이

• N개의 줄에 걸쳐서 경로가 있으면 1, 없으면 0을 출력해야한다.
• 각 정점별로 dfs를 사용하여 문제를 풀이하면 시간초과를 마주하게 된다.
• 따라서 플로이드-워셜 알고리즘을 이용하여 문제를 풀이해야 한다.
• 플로이드-워셜은 모든 정점 간의 최단 거리를 알 수 있는 알고리즘으로, 일반적으로 3중 for문을 사용하여 구현한다.
• 아래는 풀이한 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>

#define INF 100000000

int N;


std::vector<std::vector<int>> mat_mul(std::vector<std::vector<int>> a1, std::vector<std::vector<int>> a2) {
	std::vector<std::vector<int>> a3(N, std::vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int tmp = 0;
			for (int k = 0; k < N; k++) {
				tmp += (a1[i][k] * a2[k][j]);
			}
			a3[i][j] = tmp;
		}
	}
	return a3;
}

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

	std::cin >> N;

	std::vector<std::vector<int>> arr(N, std::vector<int>(N, 0));
	std::vector<std::vector<int>> result(N, std::vector<int>(N, 0));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int tmp;
			std::cin >> tmp;
			if (tmp == 0) {
				arr[i][j] = INF;
			}
			else {
				arr[i][j] = tmp;
			}
		}
	}
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = std::min(arr[i][j], arr[i][k] + arr[k][j]);
			}
		}
	}
	

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

	return 0;
}