최소 신장 트리, 크루스칼 알고리즘으로 문제를 풀었다. 크루스칼 알고리즘은 간선이 있으면 간선으로 접근하기 때문에, 간선을 먼저 생성하고 가중치가 적은 순서대로 정렬하였다. 근데, 문제를 다 풀고 나서 시간초과에 걸리게 되었는데, 간선의 정보를 담아둘 장소를 배열로 설정하느냐, 벡터로 설정하느냐에 따라 달라졌다. 처음에 접근은 전체 정점으로 트리를 구성하게 될 때 생길 수 있는 최대 간선 수를 계산하여서 배열에 할당을 하였다. 최대 간선 수 계산은 정점의 개수가 N이라고 할 때, N(N - 1) / 2로 설정하면 된다. N = 100이 최대였기 때문에, 최대 간선 수는 4950개 크기의 배열을 할당하고 시작한다. 배열의 크기를 고정시키기 때문에 불필요한 저장소 사용이 되었을 수 있다. 배열이 벡터 활용보..
전체 글
신장 트리는 정점이 N개 존재할 때, 항상 N - 1 개를 이룬다. #define _CRT_SECURE_NO_WARNINGS #include int main() { int T; scanf("%d", &T); for (int t = 0; t < T; ++t) { int N, M; scanf("%d %d", &N, &M); for (int m = 0; m < M; ++m) { int tempA, tempB; scanf("%d %d", &tempA, &tempB); } printf("%d\n", N - 1); } return 0; }
방금 프로그래머스에서 풀어본 방식인 크루스칼 알고리즘으로 풀어보았다. 여기서 좀 헷갈렸고, 놓쳤던 부분은 parent를 설정할 때 정점이 1부터 시작한다는 것으로 생각해야하고, 그래서 V + 1 사이즈로 초기화해야한다. // MST(Minimum Spanning Tree) // 최소 신장 트리는 두 종류 알고리즘으로 풀 수 있다. // 크루스칼 알고리즘 VS 프림 알고리즘 // 크루스칼 알고리즘은 간선을 선택하며 찾는 알고리즘 // 프림 알고리즘은 정점을 선택하며 찾는 알고리즘이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; long long V, E; long long getRoot(vector& par..
최소 신장 트리, C++ 최소 신장 트리, MST(Minimum Spanning Tree) 알고리즘은 두 가지 방식으로 풀 수 있다. 크루스칼 알고리즘과 프림 알고리즘이다. 크루스칼 알고리즘은 간선을 가중치가 작은 순서대로 오름차순으로 정렬을하고, 사이클을 형성하지 않는 방향으로 간선을 선택하며 트리를 구성한다. 정점이 많을 때 효과적인 알고리즘이다. 프림 알고리즘은 아무 정점을 시작 정점으로 설정한 뒤, 시작 정점의 인접 정점들 중에 가장 가중치가 작은 간선을 선택하며 정점을 잇는다. 하나의 정점을 잇게 되면, 현재까지 방문한 정점들의 인접 정점중에서 방문하지 않으면서 가장 작은 가중치를 가진 간선을 선택하는 알고리즘이다. 이렇게 되면 문제는 정점이 많아지게 된다면, 이전 방문했던 모든 정점들의 인접 ..