플로이드 와샬1 [C/C++] 백준 #1613 역사(플로이드 와샬) 이번 문제는 역사적 사건의 전후 관계가 주어졌을 때, 그 관계를 이용해서 다른 두 사건의 선후관계를 유추하는 방법입니다. 선후 관계가 있으니, 위상 정렬을 사용할 수도 있는데, 저는 그것보다는 유향 그래프라고 생각하고 플로이드 와샬(Floyd Warshall) 알고리즘을 이용했습니다. 플로이드 와샬 알고리즘을 이용하면 모든 정점 사이의 연결관계를 파악할 수 있습니다. 하지만, 알고리즘의 점근적 분석이 \(O(V^3)\)이라는 단점이 있죠. 모순이 생기지 않는 연결관계이므로 사실 \(O(V^3)\)번 반복할 필요는 없습니다. 그렇지만 그냥 오리지날 플로이드 와샬 알고리즘을 이용해서 풀었습니다. https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개.. 2022. 9. 13. 이전 1 다음
