문제 이해 단계
n개의 섬이 주어지고, 정보로는 각 섬이 이어지는 정보와 그 거리 비용이 주어진다.
이 조건에서 모든 섬을 방문할 수 있도록 선을 이을 때,
돈을 최소한으로 쓰게 하는 문제.
문제 접근 단계
해당 문제는 그림으로만 봐도 알겠지만, 가중치가 주어진 노드 문제이다.
"최소한 적은 비용을 골라라"
이 말은 그리디에서 자주 쓰는 말이어서 일단 그리디라고 가정하고 문제를 풀어보겠다.
비용을 최소화하려면 어떻게 해야 유리할까?
1. 비용이 싼 선(다리)을 고른다.
2. 선(다리)을 최대한 적게 쓴다.
2가지 일단 생각난다.
2번 조건이 확실한지 나도 잘 모르겠어서 그림을 여러 번 그려봤다.
왜냐하면 직통으로 가는 다리가 엄청 비싸고, 돌아서 가는 다리가 엄청 싸면
"돌아서 가는 게 더 싼 거 아닌가?" 이런 생각이 들었기 때문이다.
위의 상황을 연출하기 위해 이런 조건이 있다고 생각해 보자.
0 섬과 1 섬에 직통으로 가는 것은
하나의 다리만 거쳐서 갈 수 있지만 40이란 비용을 내야 한다.
돌아서 가면 다리는 많이 거치지만 더 적은 비용으로 갈 수 있다.
우리가 찾아야 하는 것은 최소의 비용, 그렇다면 2번 가정은 틀린 걸까? 아니다.
왜냐하면 모든 섬을 다 들려야 하기 때문이다.
위 문제에서 비용이 최대한 적게 들 때와,
비용이 40 드는 거리를 거쳤을 때 전체 섬을 방문하는 법을 보면
몇 개의 다리를 사용했는지 확인해 보면, 양쪽 다 3개를 사용했다.
즉, 모든 섬을 순회해야 하기 때문에 직통으로 가던,
돌아서 가던 비용이 쌀수록 유리하다.
다리를 최대한 적게 쓰면서 n개의 섬을 다 방문하려면 n-1개의 선이 필요하게 된다.
그림을 그리면서 계속해보니까 n-1개가 나오더라.. 증명은 죄송합니다.
그리고 중요한 것은 사이클(Cycle)이 발생되면 안 된다는 것이다.
사이클은 선이 모양으로 만들어져서 도형이 되는 것을 말한다.
왜 사이클을 발생하면 안 될까?
아래의 그림이 있다고 생각하자
이렇게 다리를 지었다고 하자.
여기서 1번과 3번 섬을 잇는 다리를 지어야 할까? 아니다.
왜냐하면 이미 3번은 방문을 했기 때문에
1번과 3번을 잇는 다리를 만드는 것은 말 그대로 돈 낭비가 된다.
1번과 3번 다리를 이으면 삼각형이 완성된다.
이렇게 도형이 만들어지는 것을 사이클이라고 한다.
즉 해당 문제는 이것만 생각하면 된다.
모든 섬을 방문할 때까지 비용이 적게 드는 다리부터 선택하되,
사이클을 이루는 다리는 선택하지 않는다.
이 문제의 핵심 부분이자, 끝이다.
어떻게 사이클이 발생했는지를 확인하는 방법이다.
나는 이를 자료구조 Set을 이용해서 구현하였다.
자세한 것은 문제 구현 단계에서 자세히 설명하겠다.
문제 구현 단계
// 비용을 기준으로 오름차순 정렬하도록 설계
bool compare(vector<int> a, vector<int> b){
return a[a.size()-1] < b[b.size()-1];
}
int solution(int n, vector<vector<int>> costs) {
unordered_set<int> s;
if(n == 1) return 0;
int answer = 0;
// 비용 기준 오름차순 정렬
sort(costs.begin(),costs.end(),compare);
}여기서 unordered_set을 사용한 이유는 일반적인 set은 들어온 요소들을 오름차순 정렬을 한다.
여기서는 그것까진 필요 없기 때문에 정렬을 하지 않는 unordered_set을 사용한다.
우선 들어온 벡터 costs를 정렬할 때 세 번째 값인 비용을 기준으로 오름차순 정렬하도록 했다.
그리고 n = 1일 때 그러니까,
섬이 하나일 때는 다리를 건설하지 않아도 되기 때문에 비용 0을 반환하도록 하였다.
int solution(int n, vector<vector<int>> costs) {
unordered_set<int> s;
if(n == 1) return 0;
int answer = 0;
// 비용 기준 오름차순 정렬
sort(costs.begin(),costs.end(),compare);
vector<unordered_set<int> > list(n);
for(int i = 0; i < n; i++) list[i].insert(i);
}그리고 각 노드(섬)마다 unorder_set 컨테이너를 하나씩 만든다.
해당 컨테이너 안에 들어가는 요소는, 해당 섬을 통해 갈 수 있는 섬을 뜻하는 것이다.
예를 들어, 섬 0의 unorder_set = {0,1,2}라면 섬 0을 통하면
섬 0, 섬 1, 섬 2를 갈 수 있다는 뜻이다.
그 섬과 연결된 곳, 그리고 그 연결된 곳을 통해서 갈 수 있는 섬 또한 집합에 포함된다.
그래서 set을 만들어줄 때 자기 자신(자기의 섬)은
무조건 갈 수 있기 때문에 집합에 포함시켜 준다.
for(int i = 0; i < costs.size(); i++){
// 동일 요소 발견 확인용
bool check = true;
for(auto iter : list[costs[i][0]]){
// 하나라도 발견하면 false하고 break;
if(list[costs[i][0]].count(costs[i][1])){
check = false;
break;
}
}
// 두 set의 요소가 모두 다를 때만
if(check){
// 두 set 요소를 합집합
for(auto iter: list[costs[i][0]]) list[costs[i][1]].insert(iter);
for(auto iter: list[costs[i][1]]) list[costs[i][0]].insert(iter);
// 두 요소에 연결된 요소들도 두 요소들처럼 요소들 갱신
for(auto iter: list[costs[i][0]]) list[iter] = list[costs[i][0]];
// 비용 ++
answer += costs[i][2];
}
// 다리가 n-1개 이상이 되면 종료
if(vertex >= n-1) break;
}사이클이 발생하지 않는 최저비용의 다리를 구하는 핵심 로직 부분이다.
다리의 개수만큼 반복하는데, 현재 다리는 비용이 적은 순대로 정렬된 상태다.
사이클 발생 여부를 판단하는 로직은 아래 그림으로 설명하겠다.
해당 조건이 주어졌다고 생각하고 위에서의 코드대로 로직을 돌려본다.
여기서 하고자 하는 말은 비용이 작은 다리부터 고른다는 뜻이다.
비용이 작은 다리부터 골라 그 다리에 연결되어 있는 두 섬을 각자의 Set 집합 요소로 추가해 준다.
0 섬과 1 섬이 연결됐기 때문에 0 set과 1 set은
위와 같이 두 개의 요소를 가지고
3섬과 4 섬도 마찬가지로 3,4 요소를 가질 것이다.
3번 그림도 마찬가지로 1 다음으로 비용이 낮은 2가 1 섬과 4 섬을 잇는 다리를 건설한다.
여기서 중요하게 봐야 할 점은 두 섬을 연결해 준 뒤,
두 섬과 연결되어 있는 0 섬과 3섬 또한 두 set 집합과 같은 값으로 만들어줬다는 것이다.
사실 이렇게 까진 해준 이유가 4번에서 사이클 발생 유무를 확인하게 위해서이다.
3번과 같은 로직으로 다음으로
비용이 낮은 0 섬과 3섬을 연결하는 다리를 쓰려고 하는데,
이미 두 섬을 비교해 보니 서로의 set의 같은 요소가 1개 이상 존재한다.
이렇게 같은 요소가 하나라도 존재하면 사이클이 발생한다고 정의했다.
이렇게 사이클이 발생하면 그 다리는 넘어가고 그다음 비용이 적게 드는 다리를 검사한다.
이렇게 쭉 검사해서 비용이 5가 드는 다리가 선택되는 것이다.
비용이 5가 드는 다리를 선택하고 또다시 전부 업데이트를 해주고 보니,
다리의 수가 총 4개, 즉 섬의 개수 5-1개이기 때문에 더 이상 할 필요가 없다.
그러니 반복을 끝낸다.
여기까지가 위에서의 코드다.
위 코드에 대해서는 주석을 달아놨기 때문에 로직에 대한 설명은 여기서 끝내겠다.
아래는 전체 코드를 올리고 마무리하겠다.
#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
// 비용을 기준으로 오름차순 정렬하도록 설계
bool compare(vector<int> a, vector<int> b){
return a[a.size()-1] < b[b.size()-1];
}
int solution(int n, vector<vector<int>> costs) {
unordered_set<int> s;
vector<unordered_set<int> > list(n);
for(int i = 0; i < n; i++) list[i].insert(i);
if(n == 1) return 0;
int answer = 0;
int vertex = 0;
// 비용 기준 오름차순 정렬
sort(costs.begin(),costs.end(),compare);
for(int i = 0; i < costs.size(); i++){
// 동일 요소 발견 확인용
bool check = true;
for(auto iter : list[costs[i][0]]){
// 하나라도 발견하면 false하고 break;
if(list[costs[i][0]].count(costs[i][1])){
check = false;
break;
}
}
// 두 set의 요소가 모두 다를 때만
if(check){
// 두 set 요소를 합집합
for(auto iter: list[costs[i][0]]) list[costs[i][1]].insert(iter);
for(auto iter: list[costs[i][1]]) list[costs[i][0]].insert(iter);
// 두 요소에 연결된 요소들도 두 요소들처럼 요소들 갱신
for(auto iter: list[costs[i][0]]) list[iter] = list[costs[i][0]];
// 비용 ++
answer += costs[i][2];
}
// 다리가 n-1개가 되면 종료
if(vertex >= n-1) break;
}
return answer;
}
시행착오
문제를 푸는 로직은 금방 떠올랐으나, 사이클의 발생 유무를 판단하는 코드를 짜기가 어려웠다.
만들어냈다고 생각하면, 자꾸 반례가 있고 해서 여러 번 헤맨 거 같다.
처음에는 전체 값을 업데이트하는 방식은 안 쓸려고 했는데,
문제 조건에서 섬이 최대 100개라고 해서
부담 없이 반복문을 써도 될 것 같아서 그렇게 했다.
그리디도 좀 많이 해봐야지