공급받는 것을 집합으로 생각해서 풀어야하는 문제이므로 Union-Find를 생각해주면 된다. 추가적으로 금액이 최소인 상태로 간선들을 선택하므로 느낌이 MST와 비슷하다. 다만, 발전소를 반드시 모두 거쳐야하는 것은 아니므로 스패닝 트리는 아니다. 이 문제를 정확하게 접근해보면, 한 집합안에 발전소가 1개만 있으면 된다. 적당히 priority_queue와 Union-Find를 활용해서 풀어주면 된다. #include #include #include #include #include #include using namespace std; struct DisjointSet{ vector parent, rank; DisjointSet() : parent(1001){ for(int i = 0; i < 1001; ..

사실 이 문제를 보고 가장 먼저 든 생각은 최소 스패닝 트리의 해법과 비슷하게 풀면 된다는 것이다. 특히 Kruskal 알고리즘 해법과 되게 비슷한 느낌이 들었다. 정확하게 이 문제는 스패닝 트리를 구하는 것이 아니다. 왜냐하면, 출발과 목적 지점을 포함하기만 하면 되지 모든 노드들을 전부 방문할 필요는 없기 때문이다. 하지만 Kruskal 알고리즘 기법을 활용하겠다고 마음을 먹은 이유는 다음과 같다. 1. 결과적으로 길이 최대가 되게끔 계속해서 만들어야 한다. 2. 즉 이러한 알고리즘은 사실상 최소 값들을 priority_queue에 저장하고 탐욕적으로 집합을 만드는 Kruskal 알고리즘과 매우 유사하다. 3. 또한 연결되었다는 것은 하나의 집합으로 볼 수 있다는 의미이고 상호 배타적 집합에서 배운 ..

스패닝 트리 변형 문제이다. 기본적인 아이디어는 다음과 같다. 1. MST를 구한다. (Maximum cost Spanning Tree와 Minimum cost Spanning Tree)를 구해주면 된다. 2. 이를 통해 스패닝 트리가 가질 수 있는 minimum과 maximum을 구한다. 3. 만약 k가 이 값 사이에 존재하면 사이값 정리에 의하여 존재성을 담보할 수 있다. 이유에 대해서 간략하게 살펴보면 다음과 같다. Spanning Tree에 간선을 하나 추가하게 되면 무조건 사이클이 나오게 된다. 이 상황에서 하나를 지우면 또다른 스패닝 트리가 되는데 가능성은 +-1과 0이다. 즉, 사잇값 정리에 의해서 반드시 존재성을 담보할 수 있다. 코드는 다음과 같다. #include #include #in..

전형적인 Minimum cost Spanning Tree (최소 스패닝 트리) 문제이다. 모든 지점이 연결되어야 한다는 측면에서 스패닝 트리이고, 최소 비용을 구하는 상황이므로 최소 스패닝 트리이다. 최소 스패닝 트리는 Prim 알고리즘과 Kruskal 알고리즘이 있는데, 일반적으로는 Kruskal 알고리즘을 많이 사용한다. 해당 알고리즘을 요약하자면 다음과 같다. 1. Cost 순서대로 정렬한다. 2. Cost 순으로 방문하되, 연결된 집단끼리는 하나의 집단을 형성한다. (만약 동일한 집단끼리 연결되는 경우에는 해당 경로를 제외해주면 된다.) 3. 결과적으로 모든 노드들이 하나의 집합을 형성하게 될 때 Minimum cost를 만족하게 된다. 이때, 집합에 속하냐 속하지 않냐를 기준으로 구현하는 양상을..