[백준 3116] 생물학자

문제 : 3116 생물학자

유형 : 수학, 구현

아이디어 : 입력되는 좌표가 최대 5000개이므로 각점을 모두 비교하여 몇초뒤에 만나는지 확인할 수 있다. 각 좌표들을 t초뒤에 x,y좌표로 분리하여 비교하였다.

여기서 두 점이 만나는 경우는 총 3가지로 나눠질 수 있는데

1. 한 점이 x좌표 이동이 없이 두 좌표의 y좌표 이동만으로 만나는 경우
2. 한 점이 y좌표 이동 없이 두 좌표의 x좌표 이동만으로 만나는 경우
3. 두 점이 x,y좌표 이동하여 두 점이 만나는 경우

예외처리해줄 것들이 많지만 위 3가지 경우만 걸러낼 수 있으면 답을 찾을 수 있었다. 그리고 조건에 맞는 점들을 만나는 시간과 같이 저장하여 최대 몇개의 점이 한 곳에서 만나는지 확인해주면 된다.

풀이 : 일단 각 점에 대해 x,y좌표 이동값을 구해준다.
위 1번 조건을 만족하기 위해서는 diffx가 0이면서 (yi - yj) % diffy == 0을 만족해야 한다.
2번 조건을 만족하기 위해서는 반대로 diffy가 0이면서 (xi - xj) % diffx == 0을 만족해야 한다.
3번 조건을 만족하기 위해서는 (yi - yj) / diffy == (xi - xj) / diffx을 만족해야 한다.

그 이외의 경우에는 전부 서로 만나지 못하는 점이기 때문에 continue하여 다른 점들을 확인한다.

조건을 만족하는 점들을 Data 구조체에 넣어서 arr 벡터에 따로 저장해둔다. 만나는 시간을 기준으로 오름차순 정렬을 하고 만나는 시간이 같은 좌표들을 모두 모아서 동시에 몇개의 점이 만나는 지 확인한다.

posArr는 모든 좌표들의 집합이고 c배열은 각좌표가 몇번 나오는지 체크한다. 그리고 posArr에 중복을 없앤뒤 각 좌표 중 만나는 개수가 최대인 점을 찾는다.

코드

#include <bits/stdc++.h>

const int dx[9] = {0, -1,0,1,1,1,0,-1,-1};
const int dy[9] = {0, -1,-1,-1,0,1,1,1,0};

using namespace std;
int n, M = -1, ans = 0, c[5001];
struct pos { int x, y, d; }v[5001];
map<int, int>m;

struct Data { int cnt, from, to; };
vector<Data> arr;

bool cmp(Data& a, Data& b) {
	return a.cnt < b.cnt;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i].x >> v[i].y >> v[i].d;
	}


	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int diffx = dx[v[i].d] - dx[v[j].d];
			int diffy = dy[v[i].d] - dy[v[j].d];

			if (diffx == 0 && diffy == 0) continue;
			else if (diffx == 0 && (v[i].x != v[j].x)) continue;
			else if (diffy == 0 && (v[i].y != v[j].y)) continue;
			else if (diffx == 0) {
				if ((v[i].y - v[j].y) % diffy != 0) continue;
				else {
					int temp = abs((v[i].y - v[j].y) / diffy);
					arr.push_back({ temp, i, j });
				}
			}
			else if (diffy == 0) {
				if ((v[i].x - v[j].x) % diffx != 0) continue;
				else {
					int temp = abs((v[i].x - v[j].x) / diffx);
					arr.push_back({ temp, i, j });
				}
			}
			else if ((v[i].y - v[j].y) % diffy != 0) continue;
			else if ((v[i].x - v[j].x) % diffx != 0) continue;
			else if (abs((v[i].y - v[j].y) / diffy) != abs((v[i].x - v[j].x) / diffx))continue;
			else {
				int temp = abs((v[i].x - v[j].x) / diffx);
				arr.push_back({ temp, i, j });
			}
		}
	}

	sort(arr.begin(), arr.end(), cmp);
	int idx = 0;

	while (idx < arr.size()) {
		memset(c, 0, sizeof(c));
		int pre = arr[idx].cnt;
		vector<int> posArr;
		while (idx < arr.size() && pre == arr[idx].cnt) {
			posArr.push_back(arr[idx].from);
			posArr.push_back(arr[idx].to);
			c[arr[idx].from]++;
			c[arr[idx].to]++;
			idx++;
		}

		sort(posArr.begin(), posArr.end());
		posArr.erase(unique(posArr.begin(), posArr.end()), posArr.end());
		for (int now : posArr) {
			if (M < c[now] + 1) {
				M = c[now] + 1;
				ans = pre;
			}
		}
	}

	cout << M << '\n' << ans;

	return 0;
}