11403번: 경로 찾기

Memo

로직 설명

• 플로이드-와샬을 적용시켰습니다.
• 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘이지만, 그것이 의미하는 것은 결국 모든 정점에서 모든 정점으로 갈 수 있는지 이기 때문입니다.

Code

제출 날짜

2021/05/03

메모리

2028 KB

시간

4 ms

#include <iostream>
#define endl "\\n"
int N;
bool g_map[101][101];

inline void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

inline void input()
{
	io_faster();
	std::cin >> N;
	for (int i = 0 ; i < N ; i++)
		for (int j = 0 ; j < N ; j++)
			std::cin >> g_map[i][j];
}

inline void make_floyd()
{
	for (int k = 0 ; k < N ; k++)
		for (int i = 0 ; i < N ; i++)
			for (int j = 0 ; j < N ; j++)
				if (g_map[i][k] && g_map[k][j])
					g_map[i][j] = 1;
}

inline void solve()
{
	make_floyd();
}

inline void print_val()
{
	for (int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < N ; j++)
			std::cout << g_map[i][j] << " ";
		std::cout << endl;
	}
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}