글 읽기 - 코더스 하이 고수분들 필독 부탁드립니다!!!!

vjerksen 7년 전 0

두 원 사이의 관계 중 " (원의 중심 사이의 거리) <= (두 원의 반지름의 합) " 일 때, Union & Find로 그룹지었습니다.

어디에서 논리적 오류가 있는 지, 문법 오류가 있는 지 가르침 부탁드립니다..

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<climits>
#include<set>
#include<map>
#include<deque>
using namespace std;

typedef struct{
    int x;
    int y;
    int r;
}circle;
int T,N;
vector<circle> enemy;
int ans;
int parent[3005];
int _find(int x){
    if(x == parent[x])
        return x;
    else{
        return parent[x] = _find(parent[x]);
    }
}
void _union(int u, int v){
    u = _find(u);
    v = _find(v);
    //if(u==v)    return;
    //else{
        parent[u] = v;
    //}
}
void calculate(int a, int b){
    int dist = (enemy[a].x-enemy[b].x)*(enemy[a].x-enemy[b].x) + (enemy[a].y-enemy[b].y)*(enemy[a].y-enemy[b].y);
    int comp_rt = (enemy[a].r + enemy[b].r)*(enemy[a].r + enemy[b].r);
    if(dist <= comp_rt){
        _union(a,b);
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        int temp = 0;
        ans=1;
        memset(parent,0,sizeof(parent));
        scanf("%d",&N);
        for(int i=1;i<=N;i++){
            parent[i] = i;
        }
        enemy.clear();
        enemy.resize(N+1);
        for(int i=1;i<=N;i++){
            scanf("%d %d %d",&enemy[i].x,&enemy[i].y,&enemy[i].r);
        }
        for(int i=1;i<N;i++){
            for(int j=i+1;j<=N;j++){
                calculate(i,j);
            }
        }
        sort(parent,parent+N);
        temp = parent[1];
        for(int i=2;i<=N;i++){
            if(parent[i] != temp){
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

h0ngjun7 7년 전 1

아래와 같이 수정하시면 맞을 수 있습니다.

		for (int i = 1; i<N; i++) {
			for (int j = i + 1; j <= N; j++) {
				calculate(i, j);
			}
		}
		for (int i = 1; i <= N; i++) parent[i] = _find(i);
		sort(parent + 1, parent + N + 1);
		temp = parent[1];
		for (int i = 2; i <= N; i++) {
			if (parent[i] != temp) {
				ans++, temp = parent[i];
			}
		}
		printf("%d\n", ans);

vjerksen 7년 전 0

to. appa

정말 감사합니다! 근데 질문이 하나 있는데요.

find에서 자식이 부모의 값을 저장해놔도, 부모가 새로운 부모를 가지면 기존의 부모 값을 가지던 자식들은 저장 값이 바뀌지 않는 것으로 보이는데요.

for (int i = 1; i <= N; i++) parent[i] = _find(i);

위와 같은 for문을 모든 union & find 문제에 써야하나요? 다른 간단한 방법은 존재하지 않나요?

haja 7년 전 0

parent[i] == find(i) 일때만 카운트 하는 방법이 있습니다.

vjerksen 7년 전 0

to. haja

조금만 더 설명 부탁드려도 될까요?

haja 7년 전 0

각각의 집합에 대해서 parent[i] == find(i) 즉, 부모가 자기 자신인 노드는 하나 밖에 없다는 말입니다. 그래서 이러한 노드의 개수만 세면 집합의 수를 구할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코더스 하이 고수분들 필독 부탁드립니다!!!!

vjerksen 7년 전 0

h0ngjun7 7년 전 1

vjerksen 7년 전 0

haja 7년 전 0

vjerksen 7년 전 0

haja 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말