반응형 워셜1 [백준/C++] 운동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 도시에서 시작해 다시 돌아오는 사이클이 있는지 확인하고 있다면, 그 중 가장 비용이 적은 사이클을 출력하는 문제다. 사이클을 찾기 위해서는 결국 st 에서 st로 돌아오는 최소비용을 구해야 한다. 문제는 시작점이 하나만 주어진게 아니라 모든 도시가 시작점이 될 수 있다는 점이다. 그러므로 결국 모든 도시에 대해서 시작점으로 돌아오는지 탐색을 해야한다. 처음에는 priority queue를 사용한 다익스트라 알고리즘으로 풀려고 했으나, N개의 점에 대해 다익스트라 연산을 하면 시간복잡도가 O(V*Elog(V))가 된다. [(E < V*2) 이므로 log(V)로 표현 가능] 그러면 O(V^3log(V.. 2024. 4. 23. 이전 1 다음 반응형