[플로이드 알고리즘] 경로 찾기 - 백준 11403번

11403번: 경로 찾기

바킹독 0x1C강 - 플로이드 알고리즘 참고

https://blog.encrypted.gg/1035

• 아직 강의를 보지 못함..
• 플로이드 알고리즘에 대한 자세한 내용은 다음 포스트에..

플로이드 알고리즘 : 모든 정점 쌍 사이의 최단거리를 구하는 알고리즘

for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][k] && arr[k][j]) {
                    arr[i][j] = 1;
                }
            }
        }
    }

시간 복잡도 = O(n^3)

그래프 문제 - 최단거리

• 플로이드 알고리즘
• 다익스트라 알고리즘

재귀로 풀 경우 → Timeout → 최대 O(n^3)

Solution)

• 0부터 N까지 경유지가 될 수 있는 경우를 for문 진행 O(n)
• 2중 for문 진행 O(n^2)
• i와 k가 연결되어 있고 k와 j가 연결되어 있다면 i와 j가 연결
• ⇒ if(arr[i][k] == 1 && arr[k][j] == 1) → arr[i][j] = 1
  • arr[j][i] = 1 을 할 필요 없음, i는 0~N까지 다 도니까

---

#include <iostream>

using namespace  std;
// 플로이드 알고리즘 : 모든 정점 쌍 사이의 최단거리를 구하는 알고리즘

int arr[100][100];

int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL); 

    int n;
    cin >> n;

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) {
            cin >> arr[i][j];
        }
    }
    // 경유지 k에 대해 0~k
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][k] && arr[k][j]) {
                    arr[i][j] = 1;
                }
            }
        }
    }
    cout << "-------------------------------" << endl;
    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}