글 읽기 - 50%에서 틀렸다고 하는데 이유를 모르겠습니다.

kth990303 3년 전 0

같은 진영임이 확인될 경우, 유니온 파인드로 merge해야겠다는 생각으로 코드를 짰는데,

50%에서 자꾸 틀렸다고 뜨네요.

질문게시판 반례들을 돌려보고 고치고 다시 제출해도 50%에서 틀렸다고 뜹니다.

어느 부분이 틀린걸까요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 3001;
int N, p[MAX];
vector<pair<pair<int, int>, int>> v;
// 유니온 파인드
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	p[b] = a;
	return true;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int t;
	cin >> t;
	while (t--) {
		cin >> N;
        // 초기화
		v.clear();
		v.resize(N);
		for (int i = 0; i < N; i++) {
			p[i] = i;
		}
        // 좌표, 거리 입력받음
		for (int i = 0; i < N; i++) {
			cin >> v[i].first.first >> v[i].first.second >>
				v[i].second;
		}
        // 약 O(N^2)
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				int x1 = v[i].first.first;
				int x2 = v[j].first.first;
				int y1 = v[i].first.second;
				int y2 = v[j].first.second;
				int dis = v[i].second + v[j].second;
                // 거리가 같으면 merge
				if ((x1 - x2) * (x1 - x2)
					+ (y1 - y2) * (y1 - y2) <= dis * dis) {
					merge(j, i);
				}
			}
		}
        // 부모 find해서 올바르게
		for (int i = 0; i < N; i++) {
			p[i] = find(i);
		}
		int tmp = p[0], ans = 1;    // 적 진영은 무조건 1개 이상
		sort(p, p + N);    // sort해서 진영이 다를 경우 ans++
		for (int i = 1; i < N; i++) {
			if (p[i] != tmp) {
				tmp = p[i];
				ans++;
			}
		}
		cout << ans << "\n";
	}
}

/*
질문게시판 반례
4
2
0 0 1
1 0 1
3
0 0 1
2 0 1
10 0 5
4
0 0 1
0 4 1
0 1 1
0 3 1
2
0 0 10
0 0 1
ans: 
1
2
1
1
*/

kth990303 3년 전 0

해결되었습니다.

해결방법 1. 61번째 줄과 62번째 줄 순서가 바뀌어야 한다. (sort하고 나서 기준을 잡아야됨.) (doju님 감사합니다.)

해결방법 2. 또는 merge(i, j)로 바꾸면 맞는다. acmicpc.net/board/view/27938 (원인은 아직 정확히 감이 안오네요)

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

문제

문제

출처

ICPC

50%에서 틀렸다고 하는데 이유를 모르겠습니다.

kth990303 3년 전 0

kth990303 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말