Memo
그래프 최단경로 알고리즘 중 하나인 플로이드-와샬 알고리즘입니다.
이번 문제에서는 최단거리를 찾는 것이 아니라 통행이 가능하기만 하면 되기때문에
해당 노드들이 연결되어있는지까지만 찾아주었습니다.
연결된 노드인지 확인하는 방법은
•
출발노드 : i
•
도착노드 : j
•
경유노드 : k
라고 했을 때, graph[i][j] 가 1이거나 graph[i][k] 와 graph[k][j] 모두 1인 경우에 두 노드가 연결되어 있다는 것을 알 수 있습니다.
따라서 3중 반복문을 활용해 노드들의 연결성을 계산합니다.
for (int k = 0; k < N; ++k)
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if ((graph[i][k] && graph[k][j]) || graph[i][j])
graph[i][j] = 1;
C++
복사
연결되어있다면 해당 노드도 1로 바꾸어 줍니다.
Code
제출 날짜
@5/2/2021
메모리
2148 KB
시간
4 ms
#include <iostream>
#include <vector>
int N;
std::vector<std::vector<int>> graph;
void output()
{
for (auto &i : graph)
{
for (auto &j : i)
std::cout << j << " ";
std::cout << '\n';
}
}
void solution()
{
for (int k = 0; k < N; ++k)
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if ((graph[i][k] && graph[k][j]) || graph[i][j])
graph[i][j] = 1;
}
void input()
{
std::cin >> N;
graph = std::vector(N, std::vector(N, 0));
for (auto &i : graph)
for (auto &j : i)
std::cin >> j;
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
output();
}
C++
복사