[G3] 백준 17619번 개구리 점프 C++ 그리디 알고리즘, 정렬, 분리 집합

리뷰

 

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

통나무를 그룹짓고, 두 통나무가 같은 그룹에 속하는지 여부를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• Pos : 통나무의 시작, 종료 좌표와 높이, 인덱스를 정의할 구조체, 시작 좌표를 기준으로 오름차순 정렬한다.
• w : 통나무의 정보를 저장할 Pos타입 배열
• n : 통나무의 개수를 저장할 변수
• q : 쿼리의 개수를 저장할 변수
• nodes : 각 통나무가 속한 그룹의 번호를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, q값을 입력 받고, n개의 통나무 정보를 입력 받아 w배열을 초기화한다.
2. sort함수를 통해 w배열을 시작 좌표를 기준으로 오름차순 정렬한다.
3. n개의 통나무가 속한 그룹을 자기 자신으로 오도록 nodes배열을 초기화한다.
4. 변수 mx를 정렬 후 가장 앞쪽의 통나무의 끝 좌표로, cur을 해당 통나무의 번호로 저장한다.
5. 이후 그 뒤의 통나무를 순회하며 현재 통나무의 시작 좌표가 mx보다 클 경우 mx를 현재 통나무의 끝 좌표로, cur을 해당 통나무의 번호로 저장한 뒤 continue처리한다.
6. nodes[w[i].idx]을 cur로 저장하여, 현재 통나무가 속한 그룹을 cur로 저장한다.
7. 만약 현재 통나무의 끝 좌표가 현재 그룹의 끝 좌표보다 클 경우 mx를 현재 통나무의 끝 좌표로 저장한다.
8. 그루핑이 끝나면 q개의 쿼리를 입력 받아 두 통나무가 같은 그룹에 속하면 1을, 아니라면 0을 출력한 후 개행문자를 삽입한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 통나무 A에서 다른 통나무 B로 정확히 수직 방향으로 점프할 수 있으므로 사실 y좌표는 고려하지 않아도 된다.
2. 점프할 때 다른 통나무 위를 (끝 점 포함) 지나면 안된다는 조건도 통나무를 거쳐가면 되므로 고려할 필요 없다.
3. 즉 x좌표가 이어지는 선분끼리 그룹을 짓고, 쿼리에선 두 선분이 같은 그룹에 존재하는지를 확인하면 된다.
4. 쿼리에서 통나무 번호가 1-based-indexing으로 주어지므로 비교 시 전위 감소를 시켜주었다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5;
struct Pos {
	int sx, ex, y, idx;
	bool operator<(const Pos& other) const {
		return sx < other.sx;
	}
};
Pos w[N];
int n, q;
int nodes[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		int sx, ex, y; cin >> sx >> ex >> y;
		w[i] = { sx, ex, y, i };
	}
	sort(w, w + n);

	for (int i = 0; i < n; ++i) nodes[i] = i;

	int mx = w[0].ex, cur = w[0].idx;
	for (int i = 1; i < n; ++i) {
		//cout << w[i].sx << " " << w[i].ex << " " << w[i].y << " " << w[i].idx << "\n";
		if (w[i].sx > mx) {
			mx = w[i].ex;
			cur = w[i].idx;
			continue;
		}
		nodes[w[i].idx] = cur;
		if (w[i].ex > mx) mx = w[i].ex;
	}

	//for (int i = 0; i < n; ++i) cout << nodes[i] << " ";
	//cout << "\n";

	while (q--) {
		int s, t; cin >> s >> t;
		cout << (nodes[--s] == nodes[--t] ? 1 : 0) << "\n";
	}
}