[AC] 1613 역사

출처 : https://www.acmicpc.net/problem/1613

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1613.cpp

이 문제의 경우 DFS, BFS 도 가능할것 같은 문제인데 n이 400이고 결국 모든 간선에대하여 체크해야하므로 플로이드 알고리즘을 쓰는게 더 간단한것이라고 생각했다. 

DFS나 BFS로 푼다면 조금 복잡해질것같다. 기본적으로 DP를 사용해야만 DFS는 접근이 가능할테고, BFS역시 시간문제에서 벗어나려면 상당히 애먹을것 같다. 

암튼 간단히 플로이드를 쓰면되는데 어처구니 없게 이 문제도 실수를 하였다. 날이 더워서그런지 실수가 잦다.

나의 실수는 플로이드 알고리즘에서 범위값을 for(int i=0; i<n; i++)로 잡았는데 당연히 오답이다. 왜냐면 인풋이 1부터 n까지 들어오기 때문이다. 

이 오류도 찾는데 상당히 시간이 지체되었다...ㅠㅠ

날이 더우니 정말 힘들다..ㅠㅠ