[BOJ] 20930 우주 정거장

 

20930번: 우주 정거장

2021 겨울 신촌연합 알고리즘 캠프 중급 대회에 나왔던 문제다.

대회에서 이 문제를 풀었을 때 계속 맞는 거 같은데 틀렸고 결국 시간 내에 못 풀었다.

 

대회 끝나고 풀이 방송에서 BOJ 17619-개구리 점프 문제랑 비슷하다고 하셔서 내 로직대로 일단 그 문제부터 풀었는데 맞았다.

그럼 이 문제도 맞아야 한다! 싶어서 아예 처음부터 짰는데 맞았다.

그래서 대회 때 냈던 코드를 다시 봤더니

void sol(vector<pair<pair<int, int>, int>>& arr) {
	sort(arr.begin(), arr.end(), sortby);
	pair<int, int> cur = arr[0].first;
	int curidx = arr[0].second;

	for (int i = 0; i < n; i++) {
		if (!(cur.second < arr[i].first.first)) {
			unite(curidx, arr[i].second);
			cur.second = max(cur.second, arr[i].second); //arr[i].first.second와 비교해야 함
		}
		else {
			cur = arr[i].first;
			curidx = arr[i].second;
		}
	}
}

이 함수는 서로 이동할 수 있는 우주 정거장끼리 묶어주는 데, 이를 x좌표, y좌표를 기준으로 각각 시행한다.

이 문제에서 x, y 방향 각각에 대해 좌표의 시작과 끝, 우주정거장 번호를 저장해야 해서 한 번에 저장해야 하는 데이터는 총 세 가지이다.

그래서 pair<pair<int, int>, int> 이렇게 pair를 중첩해서 pair<int, int>에는 좌표의 시작과 끝, int에는 정거장 번호를 저장하도록 했는데, 이것 때문에 실수가 생겼다.

 

cur 변수는 현재 동일한 부모를 갖도록 묶여 있는 좌표의 범위를 나타내는데, cur.first에는 그 시작, cur.second에는 끝이 저장되어 있다.

새롭게 비교한 변수가 더 넓은 범위를 포함한다면 거기에 맞게 cur도 업데이트 하는데

cur.second 값을 업데이트 할 때 끝 좌표인 arr[i].first.second과 비교해야 하는데 우주 정거장 번호인 arr[i].second랑 비교했다.

cur.second 부분 때문에 헷갈렸던 거 같다.

 

예전부터 pair 중첩하지 않고 구조체로 코드를 작성해야겠다고 생각했는데 귀찮아서 잘 안 하다가

결국 안 좋은 코딩 습관 때문에 결정적일 때 발목 잡혔다...

 

 

최근에 이 문제가 생각나서 구조체로 다시 코드 작성했다.

const int NMAX = 2e5 + 10;
vector<int> par(NMAX, -1);
void merge(int, int);
int getPar(int);

int n;
class Cordinate {
public:
	int start, end, number;

	Cordinate() {}
	Cordinate(int a, int b, int c) {
		if (a > b) swap(a, b);
		start = a;
		end = b;
		number = c;
	}
	bool operator < (Cordinate next) {
		if (start < next.start) return true;
		if (next.start < start) return false;
		return end < next.end;
	}
};

void sol(vector<Cordinate>& arr) {
	sort(arr.begin(), arr.end());
	Cordinate cur = arr[0];

	for (int i = 0; i < n; i++) {
		if (!(cur.end < arr[i].start)) {
			merge(cur.number, arr[i].number);
			cur.end = max(cur.end, arr[i].end);
		}
		else {
			cur = arr[i];
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int q;
	cin >> n >> q;
	vector<Cordinate> x, y;

	for (int i = 0; i < n; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		x.push_back(Cordinate(x1, x2, i + 1));
		y.push_back(Cordinate(y1, y2, i + 1));
	}

	sol(x);
	sol(y);

	while (q--) {
		int a, b; cin >> a >> b;
		cout << (int)(getPar(a) == getPar(b)) << ENDL;
	}

	return 0;
}

void merge(int a, int b)
{
	a = getPar(a);
	b = getPar(b);

	if (a != b) {
		par[a] = b;
	}
}

int getPar(int n)
{
	if (par[n] == -1) return n;
	return par[n] = getPar(par[n]);
}