Search
Duplicate
🍋

경로 찾기

주차
18
문제번호
11403
언어
C++
티어
실버
유형
플로이드-와샬
nj_Blog
nj_상태
이해도
풀이
풀이 O
사람
13 more properties

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++
복사