문제 개요
오늘 풀어본 문제는 프로그래머스의 '섬 연결하기'다. n개의 섬을 최소 비용으로 모두 연결하는 문제다. 그래프 이론의 최소 신장 트리(Minimum Spanning Tree) 문제와 동일하다.
문제 분석
주요 제한 사항:
•
섬의 개수 n은 1 이상 100 이하
•
costs 배열에는 [섬1, 섬2, 비용] 형태로 정보 제공
•
동일한 연결은 중복 제공되지 않음
•
모든 섬은 연결 가능함
핵심은 모든 섬을 연결하되 최소 비용을 찾는 것이다.
접근 방식
크루스칼 알고리즘을 구현하려 했다. 정확한 구현 방법이 기억나지 않아 핵심 아이디어만 차용했다.
1.
비용 기준 오름차순 정렬
2.
가장 낮은 비용부터 연결 시도
3.
연결 시 사이클 형성 여부 확인
4.
모든 섬이 연결될 때까지 반복
구현
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
bool comp(vector<int> a, vector<int> b)
{
if (a[2] < b[2])
return true;
return false;
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
vector<set<int>> groups;
sort(costs.begin(), costs.end(), comp);
for (auto cost: costs)
{
int x1 = -1, x2 = -1;
for (int i=0; i<groups.size(); i++)
{
if (groups[i].count(cost[0]))
x1 = i;
if (groups[i].count(cost[1]))
x2 = i;
}
if (x1==-1 && x2==-1) // 없으면 새로운 그룹을 생성
{
groups.push_back({cost[0], cost[1]});
answer = answer + cost[2];
}
else if (x1==-1 || x2==-1) // 한 그룹에만 속할 때
{
int x = (x1!=-1)? x1: x2;
groups[x].insert(cost[0]);
groups[x].insert(cost[1]);
answer = answer + cost[2];
}
else if (x1!=x2) // 연결해서 그룹 병합
{
set<int> new_set;
for (auto v: groups[x1])
new_set.insert(v);
for (auto v: groups[x2])
new_set.insert(v);
if (x1 > x2) {
groups.erase(groups.begin()+x1);
groups.erase(groups.begin()+x2);
} else {
groups.erase(groups.begin()+x2);
groups.erase(groups.begin()+x1);
}
groups.push_back(new_set);
answer = answer + cost[2];
}
}
return answer;
}
C++
복사
구현 과정에서 몇 가지 결정을 내렸다:
1.
set을 이용해 각 그룹(연결된 섬들)을 관리
2.
vector<set<int>>로 전체 그룹 관리
3.
새로운 연결을 시도할 때마다 그룹 병합 여부 확인
회고
1.
알고리즘 복습의 필요성
•
크루스칼 알고리즘의 정확한 구현 방법을 잊어 비효율적인 코드를 작성했다.
•
Union-Find 자료구조를 사용했다면 더 효율적인 구현이 가능했을 것이다.
2.
코드 최적화
•
현재 구현은 매 연결마다 모든 그룹을 순회하므로 비효율적이다.
•
시간 복잡도를 개선할 여지가 많다.
3.
테스트 케이스 부족
•
프로그래머스의 테스트 케이스만으로는 코드의 정확성을 완전히 검증하기 어렵다.
•
추가적인 엣지 케이스를 고려한 테스트가 필요하다.
이번 문제를 통해 알고리즘 학습의 중요성을 다시 한 번 깨달았다. 기본에 충실한 공부가 필요하다.
