[고득점Kit][그리디] 섬 연결하기 ⭐⭐⭐
카테고리: Programmers
C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges
[그리디] 섬 연결하기
난이도 ⭐⭐⭐
문제
내 풀이 ❌
이 문제는 틀린 풀이 입니다! 참고하지 마세요!ㅠㅠㅠ 틀린 풀이이긴 하지만 나중에 다시 풀기위해 기록하는 차원에서 정리한 것입니다.
이 풀이는 테스트 케이스 7번만 틀린다. 온갖 테스트 케이스 12개 가량을 추가하여 다 테스트 해봤지만 다 통과되었고 오직 프로그래머스에서 제공하는 테스트 케이스 7번만 틀렸다.. 테스트 케이스 7 번이 뭔지 알 길이 없으니 이틀 동안 계속 고민해 보았지만 그 반례를 찾지 못했다. 그래도 이 문제의 대표 풀이법이라고 하는 크루스칼 알고리즘과 얼추 비슷한 방법으로 풀었으니 그것으로 만족하고 포기해야겠다.. 흑흑… 더 이상 붙들고 있을 수는 없다. 😭 혹시 우연히 제 블로그에 방문하셔서 이 풀이의 반례를 찾아주신 분이 계시다면 ㅠㅠㅠ 댓글 간곡히 부탁드립니다ㅠㅠㅠ!!!!!!!!! 이 풀이의 문제점이 도대체 뭘지 너무 궁금하다… 나중에 한번 다시 풀어 봐야겠다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int> a, vector<int> b)
{
return a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<vector<int>> island;
sort(costs.begin(), costs.end(), compare);
island.push_back(vector<int> {costs[0][0], 1});
island.push_back(vector<int> {costs[0][1], 1});
answer += costs[0][2];
int group = 1;
for (int i = 1; i < costs.size(); i++)
{
if (island.size() == n)
{
bool flag = false;
for (int j = 0; j < island.size(); j++)
{
if (island[j][1] != 1)
{
flag = true;
break;
}
}
if (!flag) break;
}
bool vertex1Exists = false;
bool vertex2Exists = false;
int group1 = -1;
int group2 = -1;
for (int j = 0; j < island.size(); j++)
{
if (costs[i][0] == island[j][0])
{
vertex1Exists = true;
group1 = island[j][1];
}
if (costs[i][1] == island[j][0])
{
vertex2Exists = true;
group2 = island[j][1];
}
}
if (vertex1Exists && vertex2Exists && group1 == group2) // 둘 다 이미 있는데 같은 그룹 - 사이클을 형성하므로 X
continue;
if (vertex1Exists && vertex2Exists && group1 != group2) // 둘 다 이미 있는데 다른 그룹 - union 한 그룹으로 합쳐야 함
{
int minGroup = min(group1, group2);
int maxGroup = max(group1, group2);
for (int j = 0; j < island.size(); j++)
{
if (island[j][1] == maxGroup)
island[j][1] = minGroup;
}
group--;
answer += costs[i][2];
continue;
}
if (!vertex1Exists && !vertex2Exists) // 둘 다 없음 (새로운 그룹)
{
group++;
island.push_back(vector<int> {costs[i][0], group});
island.push_back(vector<int> {costs[i][1], group});
answer += costs[i][2];
continue;
}
if (vertex1Exists) // 두 번째 정점을 첫 번째 정점이 속한 그룹에 추가
{
island.push_back(vector<int> {costs[i][1], group1});
answer += costs[i][2];
continue;
}
if (vertex2Exists) // 첫 번째 정점을 두 번째 정점이 속한 그룹에 추가
{
island.push_back(vector<int> {costs[i][0], group2});
answer += costs[i][2];
continue;
}
}
return answer;
}
이 문제의 포인트
- 최소 비용으로 짓되 모든 섬을 통핼할 수 있어야 한다.
- 단 사이클이 있어선 안된다.
- 👉 즉, 다리를 여러번 건너더라도 건너 건너 도달할 수만 있으면 통행 가능하다고 보기 때문에.
- 최소한의 비용만으로 다리를 최소한으로 놓으면서 모든 섬이 통행 가능하게만 하면 되기 때문에 사이클이 있어선 안된다.
bool compare(vector<int> a, vector<int> b)
{
return a[2] < b[2];
}
sort(costs.begin(), costs.end(), compare);
costs 원소(vector)들의 2인덱스엔 다리를 짓는 비용이 들어있다. 다리를 짓는 비용에 따라 costs를 오름차순 정렬한다. 최소 비용이 드는 다리를 우선적인 후보로 선택해야 하기 때문이다.
vector<vector<int>> island; // 다리가 연결된 섬들의 모음
island.push_back(vector<int> {costs[0][0], 1});
island.push_back(vector<int> {costs[0][1], 1});
answer += costs[0][2];
int group = 1;
island: 현재 직접적인 다리가 놓아진 섬들의 모임- 각 원소들은 섬.
- 원소[0] 은 그 자체로 섬 (Vertex 번호)
- 원소[1] 은 해당 섬이 현재 속한 그룹
- 설명 예시
- [1, 4] 섬끼리 연결되어 있고 [2, 10, 19] 섬끼리 연결 되있는 상태라면, [1, 4]를 그룹 2 / [2, 10, 19]를 그룹 5 라고 하자. 두 그룹은 서로 통행할 수 없다.
- 1 과 4 는 통행 가능하고 2 와 19도 통행 가능하지만 1 과 2 는 통행 불가.
- 4 섬과 10 섬을 연결하는 다리가 나왔을 때 두 그룹을 이제 합쳐주어야 한다. 두 그룹이 서로 통행이 가능해졌으니까!
- [1, 4] 섬끼리 연결되어 있고 [2, 10, 19] 섬끼리 연결 되있는 상태라면, [1, 4]를 그룹 2 / [2, 10, 19]를 그룹 5 라고 하자. 두 그룹은 서로 통행할 수 없다.
- 설명 예시
- 각 원소들은 섬.
- 정렬을 끝낸
costs의 첫번째 원소는 가장 최소 비용으로 드는 다리의 비용이다. 따라서 이 다리는 무조건 선택하므로 일단 이 다리가 연결하는 2 개의 섬을island에 추가해준다.- 두 섬이 속한 그룹을 일단
1로 answer에 비용 누적합
- 두 섬이 속한 그룹을 일단
group: 현재 그룹 갯수. 다리 딱 하나를 둔 상태니까 현재 그룹은 1 개다. 초기값 1.
for (int i = 1; i < costs.size(); i++)
{
costs 비용 순대로 오름 차순 정렬된 다리 비용들을 살펴보며 놓을 수 있는 다리인지 없는 다리인지를 차례 차례 따질 것이다. 최소 비용 다리는 미리 놨으니 i = 1부터 시작.
if (island.size() == n)
{
bool flag = false;
for (int j = 0; j < island.size(); j++)
{
if (island[j][1] != 1)
{
flag = true;
break;
}
}
if (!flag) break;
}
- 종료 조건
island에 현재 모든 섬이 들어가 있고- 모든 섬이 다리가 놓아진 상태
- 하지만 이것 만으로는 종료조건이 되지 않는다. 모든 섬에 다리가 놓아 졌더라도 그룹이 여러개면 단절되는 섬이 있다는 얘기니까
- 모든 섬이 속한 그룹이 전부 다
1이어야 함.- 즉 모든 섬이 다 통행이 가능하게 하나의 그룹으로서 연결 되어 있는 상태면 더 이상 다리를 놓아지 않아도 되므로 종료.
bool vertex1Exists = false;
bool vertex2Exists = false;
int group1 = -1;
int group2 = -1;
for (int j = 0; j < island.size(); j++)
{
if (costs[i][0] == island[j][0])
{
vertex1Exists = true;
group1 = island[j][1];
}
if (costs[i][1] == island[j][0])
{
vertex2Exists = true;
group2 = island[j][1];
}
}
- 상태 변수. for문 지역 변수이므로 매번 다리
costs[i]마다 새롭게 선언 됨.- 해당 다리
costs[i]가 이을 수 있는 두 섬 중,costs[i][0]을 첫 번째 섬이라고 하고, 이게 기존에 다리를 한번 놓은적이 있어서island에 이미 속해 있다면vertex1Exists를 True 로 설정할 것이다. 아직까진 다리가 놓아진적이 없는 섬이라면 False. - 해당 다리
costs[i]가 이을 수 있는 두 섬 중,costs[i][1]을 두 번째 섬이라 하고 마찬가지로 기존에 다리가 놓아져 이미 연결되어 있다면vertex2Exists는 True가 되도록 할 것이다. group1👉 해당 다리costs[i]가 이을 수 있는 두 섬 중, 첫 번째 섬이 속한 그룹.- 기존에 다리를 한번 놓은적이 있어서
island에 이미 속해 있는 섬이라면 해당 섬이 현재 속해있는 그룹이 기록 될 것 - 아직까지 다리가 놓아진적이 없는 섬이라면 초기값인
-1로 남을 것.
- 기존에 다리를 한번 놓은적이 있어서
group2👉 해당 다리costs[i]가 이을 수 있는 두 섬 중, 두 번째 섬이 속한 그룹.
- 해당 다리
- for문 돌면서
island에 있는지, 즉 기존에 다리가 놓아진적이 있는 섬인지 검사하고 업뎃한다.
if (vertex1Exists && vertex2Exists && group1 == group2) // 둘 다 이미 있는데 같은 그룹 - 사이클을 형성하므로 X
continue;
- 1️⃣ 해당 다리
costs[i]가 이을 수 있는 두 섬이 다 다리가 놓아진적이 있고 And 같은 그룹이라면- 같은 그룹의 섬이라는 것은 건너 건너 연결이 되어 있는 섬이므로 여기서 또 연결해버리면 사이클이 생긴다.
- 따라서 이 같은 경우엔 다리를 놓지 않는다.
if (vertex1Exists && vertex2Exists && group1 != group2) // 둘 다 이미 있는데 다른 그룹 - union 한 그룹으로 합쳐야 함
{
int minGroup = min(group1, group2);
int maxGroup = max(group1, group2);
for (int j = 0; j < island.size(); j++)
{
if (island[j][1] == maxGroup)
island[j][1] = minGroup;
}
group--;
answer += costs[i][2];
continue;
}
- 2️⃣ 해당 다리
costs[i]가 이을 수 있는 두 섬이 다 다리가 놓아진적이 있지만 서로 다른 그룹이라면- 이제 두 그룹을 한 그룹으로 합쳐주어야 한다. 이
costs[i]다리로 인하여 서로 통행이 가능 해 질테니까. - 종료 조건을 모든 섬의 그룹이
1로 통일될 때로 할 것이기 때문에 큰 수의 그룹을 작은 수의 그룹으로 바꿔 주어 두 그룹을 합쳤다. - 그룹의 수는 1 줄어드니
group-- - 다리를 이었으므로
answer += costs[i][2] island에 추가해줄 필요는 없다. 이미 두 섬 다islad에 있으니까.- 예를 들어
- [1,4,5] 가 그룹 3 이고, [2, 8] 이 그룹 7 일 때, [1, 2] 다리를 잇게 되어 두 그룹이 합쳐진다면 [2, 8] 그룹을 7 에서 3 으로 변경한다.
group또한 7 에서 6 으로 변경될 것이다.
- [1,4,5] 가 그룹 3 이고, [2, 8] 이 그룹 7 일 때, [1, 2] 다리를 잇게 되어 두 그룹이 합쳐진다면 [2, 8] 그룹을 7 에서 3 으로 변경한다.
- 이제 두 그룹을 한 그룹으로 합쳐주어야 한다. 이
if (!vertex1Exists && !vertex2Exists) // 둘 다 없음 (새로운 그룹)
{
group++;
island.push_back(vector<int> {costs[i][0], group});
island.push_back(vector<int> {costs[i][1], group});
answer += costs[i][2];
continue;
}
- 3️⃣ 해당 다리
costs[i]가 이을 수 있는 두 섬이 모두 이전에 한번도 다리가 놓아진 적이 없다면- 이 두 섬을 새로운 그룹으로서
island에 추가해야 한다.- 그룹이 늘어났으니
group++ - 두 섬을
island에 추가하 되, 그룹은 방금 증가시킨group으로 한다.- 현재 그룹이 3 개라면, 이제 그룹 4 개가 되므로 4 로 설정하여 넣어준다.
- 그룹이 늘어났으니
- 이 두 섬을 새로운 그룹으로서
if (vertex1Exists) // 두 번째 정점을 첫 번째 정점이 속한 그룹에 추가
{
island.push_back(vector<int> {costs[i][1], group1});
answer += costs[i][2];
continue;
}
- 4️⃣ 해당 다리
costs[i]가 이을 수 있는 두 섬 中 첫 번째 섬이 이미 다리가 놓아진 섬이라면- 이제 다리가 놓아지면 첫 번째 섬이 속한 그룹에 속할 수 있으므로, 두 번째 섬만 추가하고 그룹은 첫 번째 섬이 속한 그룹으로.
if (vertex2Exists) // 첫 번째 정점을 두 번째 정점이 속한 그룹에 추가
{
island.push_back(vector<int> {costs[i][0], group2});
answer += costs[i][2];
continue;
}
- 5️⃣ 해당 다리
costs[i]가 이을 수 있는 두 섬 中 두 번째 섬이 이미 다리가 놓아진 섬이라면- 이제 다리가 놓아지면 두 번째 섬이 속한 그룹에 속할 수 있으므로, 첫 번째 섬만 추가하고 그룹은 두 번째 섬이 속한 그룹으로.
정답 풀이
1️⃣
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int> a, vector<int> b)
{
return a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
sort(costs.begin(), costs.end(), compare);
vector<bool> usedBridge(costs.size());
vector<bool> visitedIsland(n);
int answer = 0;
int numOfVisitedIsland = 0;
usedBridge[0] = true;
visitedIsland[costs[0][0]] = true;
visitedIsland[costs[0][1]] = true;
answer += costs[0][2];
numOfVisitedIsland += 2;
while(numOfVisitedIsland < n)
{
for (int i = 1; i < costs.size(); i++)
{
if (visitedIsland[costs[i][0]] && visitedIsland[costs[i][1]])
continue;
if (usedBridge[i])
continue;
if (visitedIsland[costs[i][0]] || visitedIsland[costs[i][1]])
{
usedBridge[i] = true;
visitedIsland[costs[i][0]] = true;
visitedIsland[costs[i][1]] = true;
numOfVisitedIsland++;
answer += costs[i][2];
break;
}
}
}
return answer;
}
costs를 비용 순으로 오름차순 정렬해놓는것은 같다. 이 방법은 다리 연결한 정점이 n개에 도달했는지를 검사하는 큰 while 반복문과, 차례대로 놓아도 되는 다리를 검사하기 위해 costs를 두 번째 for 반복문 이렇게 이중 for문을 사용한다. 즉, 섬 하나 연결할 때마다 새롭게 for문을 돌려 처음부터 costs를 검사한다.
- 이 문제의 포인트
- 오직 현재까지 만들어진 기준에서의
MST에 연결되어 있는 간선을 선택한다.- 이전 풀이와 다르게, 새로운 트리를 두지 않고 동일한 트리를 확장해가는 식
- 따라서 매번 새롭게
costs를 처음부터 검사한다.- 그러기 위해 이미 연결 완료된 다리를 체크해서 중복 검사하지 않도록 한다.
unBridge
- 이미 방문 완료 하여
MST에 포함되어 있는 섬도 체크 해주어야 한다.visitedIsland
- 그러기 위해 이미 연결 완료된 다리를 체크해서 중복 검사하지 않도록 한다.
- 오직 현재까지 만들어진 기준에서의
usedBridge[0] = true;
visitedIsland[costs[0][0]] = true;
visitedIsland[costs[0][1]] = true;
answer += costs[0][2];
numOfVisitedIsland += 2;
costs[0]은 무조건 선택하기 때문에 미리 체크.
costs[0]다리usedBridge[0]체크costs[0]가 잇는 두 섬 방문 체크visitedIsland[costs[0][0]],visitedIsland[costs[0][1]]costs[0]비용answer에 합numOfVisitedIsland방문한 두 섬 카운트
while(numOfVisitedIsland < n)
{
for (int i = 1; i < costs.size(); i++)
{
다리 연결한 정점이 n개에 도달했는지를 검사하는 큰 while 반복문과, 차례대로 놓아도 되는 다리를 검사하기 위해 costs를 두 번째 for 반복문 이렇게 이중 for문을 사용한다. 즉, 섬 하나 연결할 때마다 새롭게 for문을 돌려 처음부터 costs를 검사한다.
while(numOfVisitedIsland < n)
{
for (int i = 1; i < costs.size(); i++)
{
if (visitedIsland[costs[i][0]] && visitedIsland[costs[i][1]])
continue;
if (usedBridge[i])
continue;
if (visitedIsland[costs[i][0]] || visitedIsland[costs[i][1]])
{
usedBridge[i] = true;
visitedIsland[costs[i][0]] = true;
visitedIsland[costs[i][1]] = true;
numOfVisitedIsland++;
answer += costs[i][2];
break;
}
}
}
- 해당 다리가 잇는 두 섬이 이미 방문 되었으면 무시하고 지나가고, 이미 연결 완료된 다리라면 무시하고 지나간다.
- 방문 체크, 비용 합산
- 그리고 해당 반복문을 빠져나온다.
- 다시 새롭게
costs를 처음부터 검사한다.numOfVisitedIsland가n에 도달할 때 까지.
2️⃣ MST 만들기 - 크루스칼 알고리즘 사용
간선을 선택해나감.
✨ 무조건 가장 비용이 작은 간선부터 선택해 나간다는 점에서 Greedy한 알고리즘이다. 단, 선택한 간선의 두 정점이 연결되 있지 않는 경우에만 해당 간선을 선택한다. 즉, 사이클을 이루지 않도록.
MST 집합은 공백에서 시작한다.
- 가중치 순서대로 간선들을 오름차순 정렬한다.
- 오름 차순 정렬된 간선들을 차례대로 살펴보며 두 정점이 아직 연결되 있지 않는, 즉 사이클을 형성하지 않는 간선이면 선택한다. 형성한다면 그 간선은 무시하고 다음 차례로 넘어 간다.
- 정점들의 부모가 같다면(즉, 같은 그룹이라 서로 통행이 가능하다면) 사이클이 형성되는 것이고, 부모가 같지 않다면(즉, 서로 통행이 불가능 하다면) 사이클이 형성되지 않는것이다.
- Kruskal 알고리즘이 Union-Find 알고리즘과도 연관이 있는 이유.
- 선택한 간선을
MST집합에 Union 시킨다.- 2~3 과정을 선택한 간선의 수가
n-1개가 될 때까지 반복한다.
- 2~3 과정을 선택한 간선의 수가
적은 숫자의 간선을 가지는 그래프라면 크루스칼 알고리즘으로 MST를 만드는게 적합하다. 크루스칼 알고리즘은 간선을 정렬하는 시간에 좌우되기 때문이다.
정점 2와 0은 현재 통행이 가능하도록 연결 되어 있는 같은 그룹이다.(트리 개념으로 치면 부모 정점이 같은 셈이다.) 그런 상태에서 0 - 2 간선을 추가하려고 하면 사이클이 발생하므로 선택하지 않는다.
✨모든 정점의 부모 정점이 같아진다면, 즉 모든 정점이 하나의 그룹에 속하면서 통행이 가능해진다면! 즉, 하나의 트리로 합쳐져 완성된다면! 작업을 종료한다.
크루스칼 알고리즘 코드 참고 나동빈님 블로그 https://blog.naver.com/ndb796/221230994142
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int getRoot(vector<int>& parent, int x) // 인수로 넘긴 정점의 부모 정점을 알려줌
{
if (parent[x] == x) return x;
return parent[x] = getParent(parent, parent[x]);
}
void unionParent(vector<int>& parent, int a, int b) // 두 정점을 병합함. 부모가 같은, 같은 그룹으로.
{
a = getRoot(parent, a);
b = getRoot(parent, b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
bool find(vector<int>& parent, int a, int b) // 두 정점이 같은 부모를 가졌는지 확인
{
a = getRoot(parent, a);
b = getRoot(parent, b);
if(a == b) return true;
else return false;
}
bool compare(vector<int> a, vector<int> b)
{
return a[2] < b[2];
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
sort(costs.begin(), costs.end(), compare);
vector<int> parents(n);
for(int i = 0; i < parents.size(); i++)
parents[i] = i;
for(int i = 0; i < costs.size(); i++)
{
if(!find(parents, costs[i][0], costs[i][1]))
{
unionParent(parents, costs[i][0], costs[i][1]);
answer += costs[i][2];
}
}
return answer;
}
parents에서 각 인덱스는 정점을 뜻하며 원소는 해당 정점의 부모 정점을 가리킨다. 정점이 4 개라면 초기값은 [0, 1, 2, 3]으로 자기 자신이 부모다. 최종적으로 [0, 0, 0, 0]이 되어 모든 정점의 부모 정점이 같아진다면, 즉 하나의 트리로 완성되었다면 종료한다. 0 과 2 정점이 이어진다면 [0, 1, 0, 3]이 될 것이도 1 과 3 이 이어진다면 [0, 1, 0, 1]이 될 것이고 1 과 0 이 이어진다면 최종적으로 [0, 0, 0, 0]이 될 것이다.
- int getRoot(vector<int>& parent, int x)
x정점의 부모 정점을 리턴한다.
- void unionParent(vector<int>& parent, int a, int b)
- 두 정점
a,b를 같은 부모를 가진 하나의 트리로 병합한다. - 더 작은 값의 부모로 통합한다.
- 두 정점
- bool find(vector<int>& parent, int a, int b)
- 두 정점
a,b가 같은 부모를 가졌는지를 확인한다. - True 라면 또 똑같은
a - b를 잇는 간선을 추가한다면 사이클이 형성되므로 해당 간선은 선택하면 안된다.
- 두 정점
sort(costs.begin(), costs.end(), compare);
비용순서대로 가장 최소비용을 가진 간선이 앞에 오게 오름차순 정렬.
vector<int> parents(n);
for(int i = 0; i < parents.size(); i++)
parents[i] = i;
parents의 초기화는 자기 자신이 부모이게끔.
for(int i = 0; i < costs.size(); i++)
{
if(!find(parents, costs[i][0], costs[i][1]))
{
unionParent(parents, costs[i][0], costs[i][1]);
answer += costs[i][2];
}
}
- 부모가 같지 않을 때만 (같다면 이 두 정점을 추가하면 사이클이 형성되게 되므로 추가하면 안된다.)
- 두 정점을 합치기
- 기존에 이미 다른 트리에 속해 있다면 이제 그 트리와 합쳐질 것이고
- 그런적 없었다면 자기 자신이 부모인 지금 상태에서 해당 트리로 연결될 것이다.
- 비용 더해주기
- 두 정점을 합치기
3️⃣ MST 만들기 - 프림 알고리즘 사용
시작 정점에서 출발하여 정점을 선택해나감.
✨ 프림 또한 Greedy하다. 시작 할 때 시작 정점만 MST 집합에 포함시키고 현재까지의 MST 집합에 포함된 정점들 중에서 인접한 정점들 中 가중치 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 크루스칼 알고리즘은 이미 선택 완료되어 MST 집합에 들어가 있는 ‘간선’들은 다시 고려하지 않았던 반면, 프림 알고리즘은 이미 선택 완료되어 MST 집합에 들어가 있는 ‘정점’들의 인접 정점들 중에서 최소 간선을 가지는 정점을 선택하게 된다.
프림 알고리즘은 시작점을 정해놓고 시작점에서 가까운 정점들을 선택하면서 MST 를 만들어가기 때문에, 크루스칼 알고리즘과 다르게 사이클을 이루지 않는다. 정점을 선택하는 식이기 때문에 트리 하나를 처음부터 끝까지 유지하게 된다. 크루스칼 알고리즘은 최소 비용 간선을 선택하기 때문에 서브 트리가 여러개 생길 수 있고 이를 합치는 과정이 필요한데 프림 알고리즘은 인접한 정점을 선택하기 때문에 트리가 여러개 생기지 않고 단 하나의 트리를 유지하고 확장하는 식이다. 따라서 프림 알고리즘 과정에선 사이클이 생기지 않는다. 👉 사이클 검사 및 합치는 과정인 Union-Find 과정이 필요 없음.
- 시작 정점 아무거나 선택하여
MST에 포함시킨다. - 현재까지의
MST집합에 포함되어 있는 이전에 선택 완료 되었던 정점들의 인접 정점(MST에 포함되어 있지 않은)들 中 최소 가중치 간선을 가진 정점을 선택하여MST에 포함한다.- 2 번의 과정을
n-1개 간선을 가질 때까지 반복. 혹은 2 번의 과정을MST가n개의 정점을 모두 포함할 때가지 반복.
- 2 번의 과정을
코드 참고 min:D’s님 블로그 https://mind-devlog.tistory.com/89 이 분의 풀이 코드 덕분에 프림 알고리즘을 이해할 수 있었다.
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<vector<int>> graph(n, vector<int>(n));
for (int i = 0; i < costs.size(); i++)
{
graph[costs[i][0]][costs[i][1]] = costs[i][2];
graph[costs[i][1]][costs[i][0]] = costs[i][2];
}
vector<int> visited;
vector<int> unvisited;
visited.push_back(0);
for (int i = 1; i < n; i++)
unvisited.push_back(i);
for (int i = 1; i < n; i++)
{
int min = INT_MAX;
int min_index = 0;
for (int j = 0; j < i; j++)
{
for (int k = 0; k < n - i; k++)
{
if (graph[visited[j]][unvisited[k]] > 0 && min > graph[visited[j]][unvisited[k]])
{
min = graph[visited[j]][unvisited[k]];
min_index = k;
}
}
}
visited.push_back(unvisited[min_index]);
unvisited.erase(unvisited.begin() + min_index);
answer += min;
}
return answer;
}
- 시작 정점을 미리 정하고 시작한다.
- 정점을 선택해가며 하나의 트리를 확장하는 방식이므로
- 방문한 정점들을 담는
visited, 아직 방문하지 않은 정점들을 담는unvisited벡터를 따로 둔다.- 최종적으론
unvisited이 비워지고 모든 정점이visited에 속하게 된다. - 시작은
visited에 시작 정점만 속하고unvisited엔 나머지 정점들
- 최종적으론
- 방문한 정점들을 담는
vector<vector<int>> graph(n, vector<int>(n));
for (int i = 0; i < costs.size(); i++)
{
graph[costs[i][0]][costs[i][1]] = costs[i][2];
graph[costs[i][1]][costs[i][0]] = costs[i][2];
}
graph[i][j] 값은 i 정점과 j 정점 사이의 가중치(비용) 값을 담는다.
vector<int> visited;
vector<int> unvisited;
visited.push_back(0);
for (int i = 1; i < n; i++)
unvisited.push_back(i);
visited의 초기 상태는 [0]. 시작 정점을0정점으로 정해놓고 시작했다.unvisited의 초기 상태는 [1, 2, 3]이 된다.0을 제외한 나머지 정점들.- 따라서
i = 1부터 돌렸다.
- 따라서
for (int i = 1; i < n; i++)
{
int min = INT_MAX;
int min_index = 0;
for (int j = 0; j < i; j++)
{
for (int k = 0; k < n - i; k++)
{
if (graph[visited[j]][unvisited[k]] > 0 && min > graph[visited[j]][unvisited[k]])
{
min = graph[visited[j]][unvisited[k]];
min_index = k;
}
}
}
visited.push_back(unvisited[min_index]);
unvisited.erase(unvisited.begin() + min_index);
answer += min;
}
- 첫 번째 for 문 👉
n - 1번 돈다. 시작 정점 제외한 나머지n - 1개의 정점 선택 과정i는 곧 현재까지 방문한 정점의 개수가 되기도 한다.
- 두 번째 for 문 👉
visited순회visited엔i개의 방문 정점이 들어있기 때문에i까지만 검사하면 된다.
- 세 번째 for 문 👉
unvisited순회- 아직 방문하지 않은 나머지
n - i개의 정점이 들어 있다.
- 아직 방문하지 않은 나머지
visited와unvisited사이에서 인접해 있는 정점들 중 가중치가 가장 작은 간선을 가진 정점을 선택해야 한다.- 인접해 있는 정점 👉 (graph[visited[j]][unvisited[k]] > 0
- 더 작은걸 찾았다면 업데이트 👉 min > graph[visited[j]][unvisited[k]]
- 최종적으로 결정된
min을 가진unvisited정점을 삭제하고visited에 추가해야 하므로min업뎃할 때min_index에 해당unvisited정점을 보관해두어 같이 업데이트
- 최종적으로 결정된
- 결정되면
visited에unvisited[min_index]을 추가한다.unvisited[min_index]는 삭제한다.- 비용 합산
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글남기기