전체 글137 [Baekjoon] 네트워크 연결 문제 : https://www.acmicpc.net/problem/1922정점들이 주어지고, 정점간을 잇는 가중치가 주어졌을 때 모든 정점을 잇는 최소비용을 구하는 문제이다. * 풀이무방향 그래프에서 모든 정점을 잇는 간선의 비용이 최소로 되게끔 구현하는 MST구현 문제이다.일반적으로 MST문제는 Kruskal, Prim 알고리즘으로 구현한다고 배웠다. 처음에는 주어진 정점, 가중치들을 인접행렬로 나타낸 후, 가중치 순으로 오름차순 정렬하고 하나씩 이어나가는 Kruskal알고리즘으로 구현해 보았다. 그러나 cycle검사 처리를 dfs로 구현하다보니 2초라는 시간을 초과하였다. 해결책을 찾지 못하고 우선 Prim로 구현하여 해결하였다. *코드 12345678910111213141516171819202122.. 2016. 2. 9. 이전 1 ··· 15 16 17 18 다음