문제 이해 단계
https://www.acmicpc.net/problem/16398
16398번: 행성 연결
홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함
www.acmicpc.net
행성의 수 N개가 입력으로 들어온다.
이후 행성 간 관리 비용이 NxN 행렬로 들어오는데,
각각 C_ij로 i와 j 사이의 비용을 뜻한다. (i = j인 경우 0)
행성 N개를 모두 연결하는데 드는 비용을 최소화할 때, 최소화한 비용을 구하는 문제
문제 접근 단계
조건부터 보자면 행성의 수 N은 최대 1000개까지이다.
즉 NxN 행렬은 1,000,000개까지 생성될 수 있다.
그리고 C_ij는 100,000,000까지 가능하기 때문에, int 자료형이 넘을 가능성이 높다.
일단 해당 문제에서 처리해줘야 하는 것은
행렬로 들어온 행성 간에 관계성에 대해 정리해 주는 것이다.
유의미한 정보는 대각선에 존재하는 0을 기점으로 한쪽만 사용하면 된다.
이는 행렬의 특징이기도 하다.
이를 그림을 통해 나타내보자.
예제 케이스 1번을 통해 그림을 그려보겠다.
복잡하게 들어왔던 행렬 입력이, 그림으로 보니까 상당히 간단하게 변했다.
게다가 어디선가 많이 봤던 게 됐다.
그리고 사이에 있는 것도 비용이고, 이걸 최소화하는 것이 목적이다.
완전히 저번에 했던 MST(최소신장트리)와 똑같다.
최소 신장 트리와 완전히 같아졌기 때문에, 저번에 했던 문제의 링크를 올려두겠다.
이 문제와 거의 유사하게 진행하면 된다.
https://howudong.tistory.com/216
[C++] 백준 18769 - 그리드 네트워크 ( 그림으로 쉽게 이해하기 )
문제 이해 단계 https://www.acmicpc.net/problem/18769 18769번: 그리드 네트워크 재현이는 그리드 네트워크 컨설팅 회사를 운영하고 있다. 어떤 회사의 데이터 서버가 격자 형태의 그래프로 주어졌을 때,
howudong.tistory.com
요약하자면 MST를 구하기 위한 크루스칼 알고리즘을 구현한다.
크루스칼 알고리즘에선 사이클 발생 유무가 중요하기 때문에, Union & Find를 만든다.
자세한 로직은 해당 포스팅에서 자세히 설명했기 때문에
해당 포스팅을 참고해 주길 바란다.
이제 위 포스팅으로 크루스칼 알고리즘을 이해했다고 가정하고,
문제 구현 단계로 넘어가도록 하겠다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int parent[1001] = {0,};
int map[1001][1001] = {0,};
vector<pair<int,pair<int,int>>> v; // (비용,(출발지,도착지))
// 해당 노드의 루트(최종 부모)를 찾음
int find(int x){
if(parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
// union : 두 노드를 합침(부모를 같게함)
void merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return;
if(x < y) parent[y] = x;
else parent[x] = y;
}
int main(){
int N;
scanf("%d",&N);
// 시간을 줄이기 위해 미리 capcity를 할당
v.reserve(N*N+1);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++) scanf("%d",&map[i][j]);
for(int i = 0; i <= N; i++) parent[i] = i; // 초기 부모는 자기 자신
for(int i = 1; i <= N; i++){
// 행렬이기 때문에 0 이후부터 입력만 받음
for(int j = i+1; j <= N; j++){
v.push_back({make_pair(map[i][j],make_pair(i,j))});
}
}
sort(v.begin(),v.end()); // cost 순으로 오름차순 정렬
long long ans = 0; // 최대 1,000,000,000이기 때문에
// cost가 작은 것부터
for(int i = 0; i < v.size(); i++){
// 싸이클이 발생하면 패스
if(find(v[i].second.first) == find(v[i].second.second)) continue;
ans += v[i].first; // 비용 더함
merge(v[i].second.first,v[i].second.second); // 두 행성(노드)를 합침
}
printf("%lld",ans);
}MST를 크루스칼로 구현한 함수이다.
Union & Find 함수를 통해 사이클을 체크한다.
해당 함수에서 특징적으로 볼 점은
시간초과를 막기 위해 다양한 기술을 썼다는 점이다.
첫 번째는 Find 함수에서, parent [x] = find(parent [x])로 반환하는 것이다.
이 말은 재귀함수에서 계산했던 값을 parent [x]에 기록해 둠으로써,
중복된 parent [x]의 계산을 방지한다. 일종의 메모라이징이라고 볼 수 있다.
두 번째는, v.reserve(N*N+1) 일 통해 미리 capcity를 할당해 두는 것이다.
vector는 push_back을 할 때 용량이 미리 있지 않으면
사이즈를 늘리고 안에 담기 때문에 시간이 소요된다.
그래서 push_back이 많이 발생할수록 시간 소요가 많아진다.
그래서 reserve를 통해 미리 할당해 두면 시간 낭비가 훨씬 줄어들게 된다.
이 외에는 크게 다른 크루스칼 함수와 다를 것이 없다.
여기까지가 설명의 끝이다.
시행착오
가장 큰 문제점은 이 문제 자체가
MST(최소 신장 트리) 문제라는 것을 알아차리지 못했다.
행렬이 입력으로 들어와서 일단 당황했고,
아예 접근을 다르게 해 버려서 시간초과가 나도록 문제를 풀어버렸다.
두 번째 문제점은 Union Find가 익숙하지 않았다는 것이다.
이전에 비슷한(정확히는 똑같은) 문제를 풀어봤음에도
Union& FInd를 사용하는 것에 익숙하지 않아 겁을 냈다.
그래서 해당 방식을 알고 있었음에도 사용하지 않았다.
좀 더 크루스칼에 익숙해지도록 노력해야겠다.
토스아이디
toss.me