알고리즘/플로이드-워셜
플로이드 워셜 - 경로 찾기
sim0609
2023. 8. 30. 10:38
<문제>
백준 - 11403: 경로 찾기
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
<문제 접근>
플로이드 워셜 알고리즘을 이용해 모든 노드 간에 최단 경로를 탐색하면서, 노드 (i, j)에 대해 i에서 j로 가는 경로가 있는지 case를 나누어 살펴보면 된다.
Case 1. 인접 행렬 graph에서 노드 (i, j)에 대해 i에서 j로 가는 경로가 있는 경우
0 → 1로 바뀌는 경우
: graph[s][k] != 0 와 graph[s][k] != 0 을 모두 만족해야 함
Case 2. 인접 행렬 graph에서 노드 (i, j)에 대해 i에서 j로 가는 경로가 없는 경우
0 → 0으로 바뀌는 경우
: graph[s][k] != 0 와 graph[s][k] == 0 을 만족함
: graph[s][k] == 0 와 graph[s][k] != 0 을 만족함
: graph[s][k] == 0 와 graph[s][k] == 0 을 만족함
Final step. 점화식을 통한 배열 업데이트: 기존 점화식을 3중 for문의 형태로 반복하면서 배열값 업데이트
(여기서 경유지 k에 해당하는 반복문의 위치를 바꿀 경우 경로가 제대로 업데이트 되지 않음)
for 경유지 k (1~n)
for 출발 노드 S(1~n)
for 도착 노드 E(1~n)
if((graph[s][k] != 0) && (graph[k][e] != 0)){
graph[s][e] = 1
}


<전체 코드>
#include <iostream>
#include <vector>
#include <limits.h>
#include <string>
using namespace std;
vector <vector<int>> graph;
int main() {
int g, c;
cin >> g;
graph.resize(g + 1, vector<int>(g + 1));
for (int i = 1; i <= g; i++) {
for (int j = 1; j <= g; j++) {
cin >> c;
graph[i][j] = c;
}
}
for (int k = 1; k <= g; k++) {
for (int s = 1; s <= g; s++) {
for (int e = 1; e <= g; e++) {
if ((graph[s][k] != 0) && (graph[k][e] != 0)) {
graph[s][e] = 1;
}
}
}
}
for (int i = 1; i <= g; i++) {
for (int j = 1; j <= g; j++) {
if (graph[i][j] >= 1) {
cout << 1 << " ";
}
else {
cout << 0 << " ";
}
}
cout << endl;
}
}