[BOJ/Gold 4] 백준 32177 에어드롭(C++)

문제 링크

https://www.acmicpc.net/problem/32177

 

문제

2차원 평면상에 살고 있는 푸앙이는 신입생으로 대학에 입학하게 되었다. 대학에 입학한 푸앙이는 활발한 성격으로 N명의 친구들을 사귀었고, 친구들을 1번, 2번, ⋯, N번으로 부르려고 한다.

푸앙이는 그중 몇몇 친구들과 함께 사진을 찍게 되었다. 친구들에게 찍은 사진을 받고 싶지만 움직이기 귀찮은 푸앙이는 이 사진들을 가만히 앉아서 에어드롭으로 받으려고 한다.

에어드롭은 보내는 휴대폰과 받는 휴대폰 사이의 버전 차이가 T 이하이면서 유클리드 거리로 최대 K만큼 떨어진 거리의 기기에만 사진을 전송할 수 있으며, 푸앙이와 사진을 가지고 있었던 친구의 휴대폰 버전 차이가 T보다 크더라도 다른 친구들을 이용한 간접적인 경로가 있다면 사진을 전달받을 수 있다.

푸앙이는 자신이 알고 있는 N명의 친구들을 이용해 최대한 많은 사진을 전송받으려고 한다. 푸앙이가 받을 수 있는 사진을 모두 찾아보자.

 

입력

첫 번째 줄에 친구의 수 N과 에어드롭의 최대 거리 K와 최대 휴대폰 버전 차이 T가 공백으로 구분되어 주어진다.

두 번째 줄에는 푸앙이의 좌표와 푸앙이의 휴대폰 버전인 Xp, Yp, Vp가 공백으로 구분되어 주어진다.

세 번째 줄부터 N개의 줄에 걸쳐 푸앙이 친구들의 정보가 주어진다. 그중 i번째 줄에는 i번 친구의 정보 Xi, Yi, Vi, Pi가 공백으로 구분되어 주어진다. Xi, Yi는 좌표, Vi는 휴대폰 버전을 의미한다. Pi가 0이라면 푸앙이와 사진을 찍지 않았음을, 1이라면 푸앙이와 사진을 찍었음을 의미한다.

 

출력

첫 번째 줄에 푸앙이가 받을 수 있는 사진을 처음에 가지고 있었던 친구들의 번호를 공백으로 구분하여 오름차순으로 출력한다.

만약 푸앙이가 받을 수 있는 사진이 아무것도 없다면 0을 출력한다.

 

제한

•  1 ≤ N ≤ 3,000
•  0 ≤ K ≤ 30,000
•  0 ≤ T ≤ 14
•  −10,000 ≤ Xp, Yp, Xi, Yi ≤ 10,000
•  1 ≤ Vp, Vi ≤ 15
•  P ∈ {0, 1}
•  1 ≤ i ≤ N
• 주어지는 모든 좌표는 서로 다르다.
• 주어지는 모든 입력은 정수이다.

 

예제 입력 1

5 4 3
5 2 4
2 2 1 0
2 5 4 1
2 8 7 1
4 9 11 1
7 6 4 1

예제 출력 1

2 3

 

해당 그림에서 실선은 에어드롭이 가능한 경우이고, 점선은 거리는 전송이 가능하지만 버전이 호환되지 않는 경우를 나타낸다.

 

예제 입력 2

1 4 3
5 6 4
2 2 1 1

예제 출력 2

0

 

알고리즘 분류

• 유니온 파인드

 

풀이

주어진 사람은 푸앙이를 포함해서 최대 3,001명이기 때문에 중첩 for문으로 유니온 파인드를 수행해도 시간이 많이 걸리지 않는다.

여기서 유클리드 거리가 K 이하이고, 버전 차이가 T 이하인 경우에만 서로소 집합으로 연결한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 3001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct INFO {
	int X, Y, V, P;
};

int N, K, T, P;
vector<INFO> Infos;
int Parent[MAX];
vector<int> Answer;

void init() {
	for (int i = 0; i < MAX; i++) {
		Parent[i] = i;
	}
}

void input() {
    cin >> N >> K >> T;
	Infos.resize(N + 1);
	cin >> Infos[0].X >> Infos[0].Y >> Infos[0].V;
	for (int i = 1; i <= N; i++) {
		cin >> Infos[i].X >> Infos[i].Y >> Infos[i].V >> Infos[i].P;
	}
}

int findParent(int X) {
	if (Parent[X] == X) {
		return X;
	}

	return Parent[X] = findParent(Parent[X]);
}

void unionGroup(int X, int Y) {
	int ParentX = findParent(X);
	int ParentY = findParent(Y);

	if (ParentX < ParentY) {
		Parent[ParentY] = ParentX;
	}
	else {
		Parent[ParentX] = ParentY;
	}
}

void settings() {
	for (int i = 0; i <= N; i++) {
		for (int j = (i + 1); j <= N; j++) {
			double Distance = sqrt((Infos[i].X - Infos[j].X) * (Infos[i].X - Infos[j].X) + (Infos[i].Y - Infos[j].Y) * (Infos[i].Y - Infos[j].Y));
			int VersionDiff = abs(Infos[i].V - Infos[j].V);
			if ((VersionDiff <= T) && (Distance <= (double) K)) {
				unionGroup(i, j);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if ((findParent(0) == findParent(i)) && (Infos[i].P == 1)) {
			Answer.push_back(i);
		}
	}
}

void printAnswer() {
	if (Answer.empty()) {
		cout << "0\n";
	}
	else {
		for (int i = 0; i < (int)Answer.size(); i++) {
			cout << Answer[i] << " ";
		}
		cout << "\n";
	}
}

int main() {
    FASTIO

    init();
	input();
	settings();
    printAnswer();

    return 0;
}