글 읽기 - (암벽등반:2412) 구조체 정렬 틀린 부분을 모르겠어요.

cgy7096 6년 전 0

구조체를 연습하기 위해 pair <int, int> 부분을 struct point로 변경했습니다.

거기에 맞는 오름차순 정렬함수도 만들었습니다.

y를 먼저 정렬하고 x를 정렬해서, 결국 x가 같을 때는 y순으로 정렬되게끔 했습니다.

예제문제를 출력해보면 정렬도 제대로 되는 것 같은데, 왜 오답이라고 나오는지 모르겠어요.

틀린 부분을 찾아주세요.

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

struct point {
	int first;
	int second;
};

struct lessX {
	bool operator()(const point &left, const point &right) {
		return left.first < right.first;
	}
};

struct lessY {
	bool operator()(const point &left, const point &right) {
		return left.second < right.second;
	}
};

vector <point> pt;
int visited[50001] = { 0, };
int N = 0, T = 0, a = 0, b = 0;

int myabs(int n) {
	if (n < 0)
		return n * -1;
	return n;
}

int BFS() {
	queue <int> que;
	que.push(0);
	visited[0] = 1;
	while (!que.empty()) {
		int here = que.front();
		que.pop();

		if (pt[here].second == T)
			return visited[here] - 1;
		for (int i = here + 1; i <= N; ++i) {
			if (myabs(pt[i].first - pt[here].first) > 2)
				break;
			if (myabs(pt[i].second - pt[here].second) > 2 || visited[i])
				continue;
			que.push(i);
			visited[i] = visited[here] + 1;
		}
		for (int i = here - 1; i > 0; --i) {
			if (myabs(pt[i].first - pt[here].first) > 2)
				break;
			if (myabs(pt[i].second - pt[here].second) > 2 || visited[i])
				continue;
			que.push(i);
			visited[i] = visited[here] + 1;

		}
	}
	return -1;
}

void Sort() {
	sort(pt.begin(), pt.end(), lessY());
	sort(pt.begin(), pt.end(), lessX());
}

int main() {
	cin >> N >> T;
	pt.push_back(point{ 0,0 });
	for (int i = 0; i < N; ++i) {
		cin >> a >> b;
		pt.push_back(point{ a,b });
	}
	Sort();
	cout << BFS() << endl;

	return 0;
}

juhongkim2 6년 전 1

pair<int,int>를 오름차순으로 정렬한다고 하면

first를 기준으로 비교해서 작은것을 우선으로 만약 first가 같다면 second를 비교하게 됩니다.

글 읽어보니 이것을 알고 계시고 이를 구조체로 구현하기 위해 lessY, lessX로 구현하신 것 같은데

이렇게 구현하시면 정렬이 Y오름차순으로 정렬 후 X를 오름차순으로 정렬하게 됩니다.

구현 하고싶으신건 x를 우선으로 하고 x가 같으면 y를 기준으로 정렬하는것일텐데

이렇게 구현하시려면 이렇게 하시는게 맞다고 봅니다...

사실 잠깐 생각했을때 반례가 떠오르지는 않는데

이렇게 고치면 pass나옵니다

저도 구조체에서 이렇게 정렬하려고 하면 연산자는 항상 이렇게 구현하는 편입니다...

struct lessX {
	bool operator()(const point &left, const point &right) {
		if(left.first<right.first)
			return true;
		else if(left.first==right.first){
			if(left.second<right.second)
				return true;
			else
				return false;
		}
		else
			return false;
	}
};

cgy7096 6년 전 0

답변 감사합니다!!

덕분에 좋은 공부가 됬습니다~!!

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

문제

문제

출처

ICPC

(암벽등반:2412) 구조체 정렬 틀린 부분을 모르겠어요.

cgy7096 6년 전 0

juhongkim2 6년 전 1

cgy7096 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말