문제 이해 단계
https://www.acmicpc.net/problem/18769
18769번: 그리드 네트워크
재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때, 최소의 비용을 들여서 전용 통신망을 설치하려고 한다. 이때, 전용 통
www.acmicpc.net
테스트케이스 T가 주어지고, 행과 열을 나타내는 R과 C가 주어진다.
또한 입력으로 C-1개가 R번 들어오고, C개가 R-1번 들어온다.
서버와 서버 사이에는 통신망이 존재하는데
각각 이동하는데 드는 비용이 존재한다.
설치 비용은 무조건 1,2,3,4 중 하나이다.
그리고 한 서버와 연결된 통신망(간선)의 비용은 중복되지 않는다.
이런 조건에서 모든 서버가 통신할 수 있도록 하는 최소 비용을 구하는 문제
문제 접근 단계
일단 그래프 노드와 같은 그림이 주어지고, 간선에 대한 비용이 주어진다.
그리고 간선을 따라서 모든 서버가 통신할 수 있도록 하는 최소 비용을 구하라는 것
대놓고 최소 신장 트리(MST) 알고리즘을 사용하라는 문제이다.
그래서 최소 신장 트리를 구하기 위해, 대표적으로 사용하는 크루스칼 알고리즘을 사용한다.
그래서 크루스칼 알고리즘을 위해 만들어야 하는 함수들을
간략하게 설명하고 바로 문제 구현 단계로 넘어가겠다.
크루스칼 알고리즘 로직
크루스칼 알고리즘은 가중치를 오름차순으로 정렬하여 간선들을 고르는데,
사이클이 발생하지 않는 간선들만 선택하여 최소 가중치를 구하는 것이다.
예를 들면 위 그림과 같이 가중치가 있는 간선과 노드가 있다고 하자.
그러면 간선의 가중치가 적은 순서에 따라 간선을 고른다.
여기서 가중치가 2인 간선은 순서가 바뀌어도 상관없다.
여기까지는 고르는 데에 문제가 없다. 사이클이 발생하지 않기 때문이다.
사이클이 발생한다는 것은 아래와 같은 현상을 말하는 것이다.
다른 식으로 말하면, 3개의 노드가 계속해서 순환(사이클)을 이룬다.
이런 경우를 제외시켜 주는 것이다.
그래서 사이클을 이루는 위의 두 경우를 제외하고
다음을 보면
이렇게 다음 순위에 있는 가중치 5를 이어주면
이제 모든 노드가 연결되어 알고리즘이 종료된다.
그래서 이때까지의 가중치를 모두 더해주면 10이 나온다.
크루스칼 알고리즘은 이런 로직으로 돌아간다.
사이클 구현
위에서 보았듯이, 결국 중요한 것은 사이클이 발생하는지를 확인하는 것이다.
즉, 사이클을 구현하는 것이 중요하다.
어떻게 사이클을 구현할 수 있을까?
자신의 부모 노드를 나타내는 parent [] 배열을 만들어, 자신의 부모를 표시한다.
이때 나타내는 부모는 단순히 자신 위에 있는 부모가 아닌,
가장 위에 있는 최종적인 부모여야 한다.
그렇게 해야, 두 노드가 중복인지 확인할 수 있고,
유니온을 통해 두 집합을 합칠 수 있다.
사이클을 확인하는 방식은 쉽게 말해서
확인하는 두 노드의 부모가 같은지를 확인하는 것이다.
아무것도 하지 않은 초기화된 노드와 간선들이다.
parent배열은 기본적으로 자기 자신을 가리키도록 초기화된다.
예를 들어, parent [1] = 1 이런 식으로 말이다.
위쪽 행이 노드의 번호, 아래쪽 행이 해당 노드의 부모 노드이다.
1번 노드와 2번 노드를 연결한다고 가정한다.
노드 번호가 더 작은 1번 노드를 부모 노드로 삼는다.
그래서 밑에 표를 보면 노드 2번의 부모 노드를 1번으로 바꾼다.
이를 코드로 나타내면 parent [2] = 1로 된 것이다.
이번에는 1번 노드와 3번 노드의 간선을 연결한다.
이때까지는 parent [1] = 1이고,
parent [3] = 3이었기 때문에 두 부모가 같지 않았다.
위와 마찬가지로 노드 번호가
더 작은 1번 노드를 부모 노드로 삼는다.
아래도 똑같이 노드 3번의 부모 노드를 1번으로 바꾼다.
parent [3] = 1
마지막으로 3번 노드와 2번 노드를 연결하려고 했다.
그런데 parent [2] = 1이고, parent [3]= 1로 두 노드의 부모가 같다.
즉, 해당 노드를 연결하는 것은
사이클을 발생시키므로 연결시킬 수 없다.
이런 식으로 사이클이 발생하는 것을 확인할 수 있다.
이제 중요한 개념들은 다 했으므로,
이제 문제 구현 단계에서 나머지를 다뤄보겠다.
사실 유니온 파인드(Union & Find)도 해야 하지만,
해당 개념들은 코드로 보는 것이 훨씬 낫기 때문에 문제 구현 단계에서 설명하겠다.
문제 구현 단계
// 입력 정보를 담은 구조체
struct NetWork{
int start; // 출발 노드
int end; // 도착 노드
int price; // 비용
};
vector<NetWork> lines; // 간선 정보
int R,C;
// 2차원 입력을 1차원으로 바꿔서 간선 정보를 저장
void getRelation(){
for(int i = 0; i < R; i++){
for(int j = 0; j < C-1; j++){
int start = C*i+j;
int end = C*i+j+1;
int price;
cin >> price;
lines.push_back({start,end,price});
}
}
for(int i = 0; i < R-1; i++){
for(int j = 0; j < C; j++){
int start = C*i+j;
int end = C*(i+1)+j;
int price;
cin >> price;
lines.push_back({start,end,price});
}
}
}3가지로 들어오는 입력 정보를 하나로 처리하기 위해
Network라는 구조체를 선언해 줬다.
그리고 간선 정보를 모두 모아주고
나중에 정렬해 주기 위해 lines이라는 벡터를 선언해 줬다.
여기서 중요한 것은 2차원 입력으로 들어왔던 것을 1차원으로 변환시켜 주는 것이다.
그래서 여기에 쓰이는 것이 C*i+j이다.
start와 end에 맞게 적절히 써줘야 한다.
int parent[500*500+1]; // 2차원 배열을 1차원으로 바꿈
// 루트 부모(최종 부모)를 찾음
int findParent(int x){
if(parent[x] == x) return x;
return findParent(parent[x]);
}
//유니온 함수(두 노드 병합) -> 부모를 공유
void merge(int x, int y){
// 루트까지 올라감
int parentX = findParent(x);
int parentY = findParent(y);
// 노드 번호가 낮은 걸 부모로 삼음
if(parentX < parentY) parent[parentY] = parentX;
else parent[parentX] = parentY;
}위에서 코드로 설명한다는 Find 함수인 findParent와 Union 함수인 merge이다.
Union 함수는 Find 함수를 기반으로 사용한다.
Union 함수는 간단하게 말하자면 아래와 같다.
루트 노드(최종 부모) 노드까지 올라가서,
그 근간을 합쳐버림으로써 그 아래에 있는 하위요소들이 자동적으로 합쳐지게 하는 것이다.
Find는 더 이상 부모 노드가 없을 때까지 재귀함수를 반복하는 것이다.
// 비용순으로 오름차순
bool compare(NetWork a, NetWork b){
return a.price < b.price;
}
sort(lines.begin(),lines.end(),compare); // 오름차순 정렬
// 간선 비용 작은 순으로 더하기
for(int i = 0; i < lines.size(); i++){
int a = lines[i].start;
int b = lines[i].end;
// 싸이클 발생시 패스
if(findParent(a) == findParent(b)) continue;
merge(a,b); // 두 노드 병합
ans += lines[i].price; // 비용 더하기
}정렬 규칙을 만드는 compare 함수와 해
당 코드는 main 함수 안에 있는 정답을 구하는 코드이다.
비용에 따라 오름차순 정렬하여 간선을 정렬한 뒤, 그 순으로 하나씩 호출한다.
그리고 그 간선과 연결되어 있는 출발 노드와 도착 노드의 사이클 발생을 비교하면서 비용을 더하고 합한다.
여기까지가 모든 설명의 끝이다.
이제 아래에 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 입력 정보를 담은 구조체
struct NetWork{
int start; // 출발 노드
int end; // 도착 노드
int price; // 비용
};
vector<NetWork> lines; // 간선 정보
int parent[500*500+1]; // 2차원 배열을 1차원으로 바꿈
int R,C;
// 비용순으로 오름차순
bool compare(NetWork a, NetWork b){
return a.price < b.price;
}
// 초기화 함수
void init(){
for(int i = 0; i < R*C; i++) parent[i] = i;
lines.clear();
lines.reserve(R*C);
}
// 2차원 입력을 1차원으로 바꿔서 간선 정보를 저장
void getRelation(){
for(int i = 0; i < R; i++){
for(int j = 0; j < C-1; j++){
int start = C*i+j;
int end = C*i+j+1;
int price;
cin >> price;
lines.push_back({start,end,price});
}
}
for(int i = 0; i < R-1; i++){
for(int j = 0; j < C; j++){
int start = C*i+j;
int end = C*(i+1)+j;
int price;
cin >> price;
lines.push_back({start,end,price});
}
}
}
// 루트 부모(최종 부모)를 찾음
int findParent(int x){
if(parent[x] == x) return x;
return findParent(parent[x]);
}
//유니온 함수(두 노드 병합) -> 부모를 공유
void merge(int x, int y){
// 루트까지 올라감
int parentX = findParent(x);
int parentY = findParent(y);
// 노드 번호가 낮은 걸 부모로 삼음
if(parentX < parentY) parent[parentY] = parentX;
else parent[parentX] = parentY;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--){
int ans = 0;
cin >> R >> C;
init();
getRelation();
sort(lines.begin(),lines.end(),compare); // 오름차순 정렬
// 간선 비용 작은 순으로 더하기
for(int i = 0; i < lines.size(); i++){
int a = lines[i].start;
int b = lines[i].end;
// 싸이클 발생시 패스
if(findParent(a) == findParent(b)) continue;
merge(a,b); // 두 노드 병합
ans += lines[i].price; // 비용 더하기
}
cout << ans << "\n";
}
}
시행착오
처음에는 백트래킹으로 풀어보려고 했는데, 안 됐다.
정확히는 맞게 푼 것 같은데 백준에서는 계속 아니란다. 아마 분명 예외케이스가 있었던 것이겠지.
이건 MST로만 풀라고 만든 문제 같다. 하긴 못 알아챈 내가 바보지.
크루스칼 알고리즘을 제대로 공부하지 않은 게 잘못인 것 같다.
수업시간에 좀 제대로 할걸. 왜 까먹어가지고..
고생고생해서 백트래킹했는데, 또 실패했다.
요즘 왜 백트래킹밖에 생각이 안 나지.
그거면 다 풀릴 것 같은데 그걸로 풀린 적이 없다.