[C++] 20652: Stuck in a Rut

USACO 2020 December Contest
Bronze Problem 3. Stuck in a Rut

20652번: Stuck in a Rut

(https://github.com/womogenes/usaco-december-2020-bronze)를 참조하여 풀었다.

풀이

조건

1. 소들은 x, y 좌표가 겹치지 않는다.
2. 방향(E or N)이 다른 소들끼리만 간섭 가능하다.

주요 로직

1. 방향을 기준으로 소들을 2가지 벡터로 분류한다.
2. North 방향의 소는 X좌표를 기준으로, East 방향의 소는 Y좌표를 기준으로 오름차순 정렬한다.
3. 각 North와 East 소들에 대해서: eastCow가 오른쪽 위, northCow가 왼쪽 아래에 있을 경우 만날 가능성이 있으므로 둘 중 하나가 정지하는 위치를 체크한다.
   a. 만나는 지점까지 eastCow가 더 멀리 있으면서, eastCow가 이전에 정지하지 않았을 경우:
   -> eastCow가 정지한다. 만난 northCow보다 왼쪽에 있는 northCow는 이전 바깥 for문에서 모두 확인하였으므로, 현재 만난 northCow가 현재 eastCow를 멈추게 한다.
   b. 만나는 지점까지 northCow가 더 멀리 있으면서, eastCow가 이전에 정지하지 않았을 경우:
   -> 현재 northCow보다 왼쪽에 있는 northCow들이 eastCow를 멈추게 하지 않았으므로, 현재 northCow가 정지한다. 현재 northCow가 정지하였으므로, 더 위쪽의 eastCow를 멈추게 하지 못한다. 따라서 현재 northCow에 대한 확인을 멈춘다.(break)

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000001
#define FOR(i, n) for(int i = 0; i < n; i++)

using namespace std;

struct Cow {
	int x;
	int y;
	int id;
};

struct Stop {
	int x;
	int y;
};

bool ascendingX(Cow a, Cow b) {
	return a.x < b.x;
}

bool ascendingY(Cow a, Cow b) {
	return a.y < b.y;
}

vector<Cow> eastCows;
vector<Cow> northCows;
vector<Stop> stops(50, {0, 0});
vector<int> result(50, INF);

int main(void) {
	int n;
	cin >> n;
	FOR(i, n) {
		char direction;
		int x, y;
		cin >> direction >> x >> y;
		if (direction == 'E') eastCows.push_back({x, y, i});
		if (direction == 'N') northCows.push_back({x, y, i});
	}

	sort(northCows.begin(), northCows.end(), ascendingX); // northCow는 x좌표 오름차순
	sort(eastCows.begin(), eastCows.end(), ascendingY); // eastCow는 y좌표 오름차순
	
	// 각 northCow에 대한 eastCow의 충돌 확인
	for (auto northCow: northCows) {
		for (auto eastCow: eastCows) {
			if (eastCow.x < northCow.x && northCow.y < eastCow.y) {
				int eastDist = northCow.x - eastCow.x;
				int northDist = eastCow.y - northCow.y;
				if (northDist < eastDist && stops[eastCow.id].x == 0) { // eastCow가 정지 && 이전의 northCow에서 정지한 적 없음
					stops[eastCow.id] = {northCow.x, eastCow.y};         // eastCow의 정지 위치 표시
				} 
				if (eastDist < northDist && stops[eastCow.id].x == 0) { // northCow가 정지 && 겹친 eastCow는 이전에 정지한 적 없음
					stops[northCow.id] = {northCow.x, eastCow.y};      // northCow의 정지 위치 표시. 정지하였으므로 다음 northCow로 넘어감.
					break ;
				}
			}
		}
	}

	for (auto eastCow: eastCows)
		if (stops[eastCow.id].x != 0)
			result[eastCow.id] = stops[eastCow.id].x - eastCow.x;
	for (auto northCow: northCows)
		if (stops[northCow.id].x != 0)
			result[northCow.id] = stops[northCow.id].y - northCow.y;
	
	FOR(i, n) {
		if (result[i] == INF)
			cout << "Infinity\n";
		else
			cout << result[i] << '\n';
	}

	return (0);
}