역사

[백준 1613] 역사 C++

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 사건들의 전후 관계를 파악하는 문제라서 처음에 바로 위상 정렬로 풀기 시작했었다. 근데 위상 정렬을 해놓으니 관계도는 명확히 그려지지만 임의의 정점 2개를 선택했을 때 해당 정점들이 서로 어떤 관계에 있는지 알아보려면 매번 BFS가 필요해 보였다. 효율이 안 좋게 느껴졌고 위상 정렬은 아닌 것 같아 알고리즘 분류를 켜서 어떤 알고리즘을 써야 하는지 힌트를 받았다. 플로이드-와샬 알고리즘을 쓰는 문제였다. N이 400..