(백준 알고리즘 문제풀이) 10775번 공항
by 줌코딩
문제
문제 접근
- 이 문제를 풀다가 disjoint set이 떠올랐다면, union-find 알고리즘이 떠올랐다면 당신은 대단한 사람이다!
- 4번이 비어있고 도킹되는 위치를 4라고 하면 4번은 도킹되고 4번을 도킹하려 할때의 결과물은 3번을 도킹하려할 때와 같이 1~3번 사이를 봐야한다.
- 즉 4번이 도킹되면서 4-1인 3과 union되는 것으로 볼 수 있다!
초기 union-find 코드
#include <cstdio>
int P[500001], par[500001], g, p;
int find(int i){
if(par[i] == -1)return i;
return find(par[i]);
}
int main(){
scanf("%d %d", &g, &p);
for(int i = 0; i < g + 1; i++)par[i] = -1;
for(int i = 0; i < p; i++)scanf("%d", &P[i]);
for(int i = 0; i < p; i++){
int x = P[i];
int px = find(x);
if(!px){
printf("%d", i);
return 0;
}
int py = find(px - 1);
par[px] = py;
}
}
- 오히려 느려졌다… 15%에서 시간초과가 뜨게 된다..!
개선된 find 코드
int find(int i){
if(par[i] == -1)return i;
return par[i] == find(par[i]);
}
- find를 하면서 중간다리도 다 업데이트 시켜줌으로써 시간이 엄청 빨라지게 된다.
최종 코드
int find(int i){
if(par[i] == i)return i;
return par[i] = find(par[i]);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> g >> p;
for(int i = 0; i < g + 1; i++)par[i] = i;
for(int i = 0; i < p; i++){
cin >> x;
int px = find(x);
if(!px)break;
//Union
par[px] = find(px - 1);
ans ++;
}
cout << ans;
}
느낀점
- 이전에 union find 알고리즘을 사용할 때도 중간에 업데이트 시켜주지는 않았는데 오히려 저렇게 하는 게 시간이 훨씬 덜 걸리는 걸 보고 조금은 충격을 먹었다.
- 나중에 union-find를 사용할 때도 같은 방식으로 중간중간 업데이트 할 수 있게 해야겠다.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS