문제 이해 단계
https://www.acmicpc.net/problem/13905
섬 위에 N개의 집과 M개의 다리가 존재한다.
그리고 각 다리에는 무게 제한 K가 걸려있다.
입력으로 출발지와 목적지가 주어지는데,
혜빈이는 최대한 많은 금빼빼로를 들고 목적지까지 도착해야 한다.
각 다리에서 무게제한까지만 빼빼로를 들 수 있을 때
최대 몇 개까지 빼빼로를 옮길 수 있는가?
문제 접근 단계
제한사항부터 살펴보자.
존재하는 집의 수(N)는 100,000개, 다리의 수(M)는 300,000이다.
최대 10^5 * 10^5 = 10^10이므로, 완전탐색으로 하면 시간초과가 뜬다.
따라서 하나하나 비교하는 것은 안되고, 다른 방법이 필요하다.
그래프 탐색
결국엔 집과 집을 연결하는 것이 다리고, 그 다리에는 무게라는 것이 존재한다.
이를 다르게 표현하면 정점과 정점 사이에 간선, 그리고 가중치로 바꿔 말할 수 있다.
즉 그래프 탐색을 하는 문제로 볼 수 있다는 소리이다.
가능한 경로
그래프 탐색 관점에서 이 문제를 바라보자.
각 정점에서 방문하지 않은 정점 중에 가중치가 가장 큰 쪽으로 가야 한다.
그렇게 방문하면서 출발지에서 도착지까지 가야 한다.
즉, 출발지에서 도착지로 이어지는 경로 중,
가중치의 합이 가장 높은 경로를 찾아야 한다는 것이다.
그래프 탐색에서 이럴 때 크루스칼 알고리즘을 사용할 수 있다
크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하는 알고리즘인데,
이를 변형하면 모든 정점들을 가장 높은 비용으로 연결할 수 있다.
모든 정점들을 연결할 수 있는 경우 중, 가장 높은 가중치의 합을 크루스칼로 구한 후,
출발노드에서 하여금 다시 한번 BFS나 DFS를 통해 가중치의 최솟값을 구하게 하면 된다.
로직 그림 설명
문제에 나와있던 예시 그림을 가져왔다.
해당 그림을 아래와 같이 크루스칼 알고리즘으로 최대 비용을 가지는 경로를 찾는다.
모든 정점을 연결하면서, 사이클을 발생시키지 않으면서, 최대비용을 가진다.
이 단계는 모든 정점을 연결한 거지, 출발지에서 도착지까지 연결한 것이 아니다.
이제 출발지부터 시작해서 도착지까지, 가중치가 가장 작은 것을 찾기 위한 BFS를 돌린다.
출발지 1부터 5까지 크루스칼 경로에서 최솟값은 3이 된다.
이런 식으로 답을 찾으면 된다.
이제 문제 풀이 단계에서 코드로 구현해 보자.
문제 구현 단계
// 노드1, 노드2, 가중치
struct Info{
int n1;
int n2;
int w;
};
vector<Info> v;
vector<pair<int,int>> node[100001];
// 가중치의 내림차순 정렬
bool compare(Info a, Info b){
return a.w > b.w;
}
int set[100001]; // 해당 원소의 부모
// 최종 부모를 찾는 함수
int getParent(int x){
if(set[x] == x) return x;
return getParent(set[x]);
}
// 싸이클을 이루는지 판단
bool isSame(int a, int b){
a = getParent(a);
b = getParent(b);
if(a==b) return true;
else return false;
}
// 두 집합을 합치는 union
void merge(int a, int b){
a = getParent(a);
b = getParent(b);
// 노드 값이 작은 것을 부모로 함
if(a < b) set[b] = a;
else set[a] = b;
}
// 크루스칼 알고리즘
void kruskal(){
sort(v.begin(),v.end(),compare); // w의 내림차순 정렬
// 부모 값 자기 자신으로 초기화
for(int i = 1; i <= N; i++) set[i] = i;
for(int i = 0; i < v.size(); i++){
int n1 = v[i].n1;
int n2 = v[i].n2;
int w = v[i].w;
// 싸이클을 이루지 않으면 두 노드를 연결(간선 연결)
if(!isSame(n1,n2)){
merge(n1,n2);
node[n1].push_back({n2,w});
node[n2].push_back({n1,w});
}
}
}크루스칼 알고리즘을 구현한 부분이다.
Union-Find를 구현했다는 것이 맞는 말인 것 같다.
어떤 원소의 부모를 뜻하는 set배열을 만들어두고,
가중치의 내림차순 정렬하기 위한 정렬 규칙 compare를 만들어뒀다.
isSame으로 두 집합의 부모가 같은지 판단하여, 사이클을 이루는지 확인한다.
사이클을 이루지 않는다면 두 집합을 합쳐서 노드(다리)를 연결한다.
이 과정을 반복한다.
노드를 이어 node라는 벡터로 새로운 그래프를 만든다.
int bfs(){
int visited[N+1];
// 무한대 값으로 visited 배열 초기화
fill(visited,visited+N+1,INF);
queue<int> q;
q.push(sNode); // 출발지 큐에 넣음
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0; i < node[x].size(); i++){
int nx = node[x][i].first;
int w = node[x][i].second;
if(visited[nx] != INF) continue;
// 둘 중 더 작은 가중치를 visited에 넣음
visited[nx] = min(w,visited[x]);
q.push(nx);
}
}
return visited[eNode];
}다음은 크루스칼로 만든 node 그래프를 BFS를 돌린다.
BFS를 돌리면서 visited배열에 가중치의 최솟값을 저장한다.
가중치의 최솟값을 저장하기 위해 처음에 visited배열은 INF로 초기화해 둔다.
핵심적인 코드 설명은 여기까지이다.
이제 아래에 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 99999999
// 노드1, 노드2, 가중치
struct Info{
int n1;
int n2;
int w;
};
int N,M,sNode,eNode;
vector<Info> v;
vector<pair<int,int>> node[100001];
bool visited[100001] = {false,};
// 가중치의 내림차순 정렬
bool compare(Info a, Info b){
return a.w > b.w;
}
int set[100001]; // 해당 원소의 부모
// 최종 부모를 찾는 함수
int getParent(int x){
if(set[x] == x) return x;
return getParent(set[x]);
}
// 싸이클을 이루는지 판단
bool isSame(int a, int b){
a = getParent(a);
b = getParent(b);
if(a==b) return true;
else return false;
}
// 두 집합을 합치는 union
void merge(int a, int b){
a = getParent(a);
b = getParent(b);
// 노드 값이 작은 것을 부모로 함
if(a < b) set[b] = a;
else set[a] = b;
}
// 크루스칼 알고리즘
void kruskal(){
sort(v.begin(),v.end(),compare); // w의 내림차순 정렬
// 부모 값 자기 자신으로 초기화
for(int i = 1; i <= N; i++) set[i] = i;
for(int i = 0; i < v.size(); i++){
int n1 = v[i].n1;
int n2 = v[i].n2;
int w = v[i].w;
// 싸이클을 이루지 않으면 두 노드를 연결(간선 연결)
if(!isSame(n1,n2)){
merge(n1,n2);
node[n1].push_back({n2,w});
node[n2].push_back({n1,w});
}
}
}
int bfs(){
int visited[N+1];
fill(visited,visited+N+1,INF);
queue<int> q;
q.push(sNode);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0; i < node[x].size(); i++){
int nx = node[x][i].first;
int w = node[x][i].second;
if(visited[nx] != INF) continue;
visited[nx] = min(w,visited[x]);
q.push(nx);
}
}
return visited[eNode];
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N >> M;
cin >> sNode >> eNode;
for(int i = 0; i < M; i++){
int v1, v2, v3;
cin >> v1 >> v2 >> v3;
v.push_back({v1,v2,v3});
}
kruskal();
int ans = bfs();
if(ans == INF) cout << "0";
else cout << ans;
}시행착오
DFS로 풀다가 실패했다.
시간초과가 날 건 예상했는데 틀렸습니다가 떠서 당황했다.
로직적으로는 틀린 게 없는 것 같은데,
차라리 시간초과라도 떴으면 인정이라도 했을 텐데..
크루스칼 알고리즘.. 미리미리 알아둘걸..
그래도 이번 기회에 확실히 안 것 같아서 다행인 것 같다.
union-find 계속 내 발목을 잡는 것 같다.
생활비..