Boj 3043) 장난감 탱크

문제

백준 3043

설명

이 문제는 탱크끼리 충돌이 나면 안된다. 하지만 간단하게 충돌이 허용된다고 가정하고 생각해보자.

우선 각 축의 좌표마다 하나씩 탱크가 반드시 가야한다. 어떻게 가장 적게 움직이면서 좌표마다 탱크를 보낼 수 있을까?

이는 그리디 전략으로 쉽게 구성할 수 있다. 탱크를 축에 대해 정렬을 해서 순서대로 좌표를 배정하는 것이다. 예를들어 X 축을 오름차순으로 즉 1번 좌표부터 n 번 좌표까지 배정을 한다면, 가장 작은 x 를 가진 탱크부터 1번 좌표에 배정하면 된다. 증명은 정렬과 역순으로 배치된 두 탱크가 있을 때 이를 정렬 순으로 바꾸면 무조건 비용이 싸짐을 이용하면 쉽게 될 듯 하다.

이제 탱크끼리의 충돌을 생각해보자. 오름차순으로 정렬된 순서대로 선택한 탱크의 좌표를 t 라고 하고 차례로 배치할 좌표를 v 라고 하자.

• t > v 의 경우 충돌이 일어나지 않는다. 움직일 방향이 음의 방향인데 정렬된 순서로 탱크를 선택하기 때문에 도착할 좌표까지 탱크가 없음이 보장되기 때문이다.
• t < v 의 경우 충돌이 일어날 수 있다.

이는 정렬된 순서에 따라서 해소할 수 있는 문제다. 각 축마다 오름차순과 내림차순 각각에 대해서 그리디 전략을 취해주면 된다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

struct Item {
	int idx, coord[2];
	inline int& operator[](int i) { return coord[i]; }
} items[501];
int n;

vector<pair<int, char>> ans;
inline void Move(int idx, char d) { ans.push_back({ idx, d }); }

int main(void)
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> items[i][0] >> items[i][1];
		items[i].idx = i+1;
	}

	for (int axis = 0; axis < 2; axis++)
	{
		sort(items, items + n, [axis](Item& a, Item& b) {return a[axis] != b[axis] ? a[axis] < b[axis] : a[!axis] < b[!axis]; });
		for (int i = 0, cur_x = 1; i < n; i++, cur_x++)
			if (items[i][axis] >= cur_x)
			{
				for (int j = 0; j < abs(items[i][axis] - cur_x); j++)
					Move(items[i].idx, axis == 0 ? 'U' : 'L');
				items[i][axis] = cur_x;
			}

		sort(items, items + n, [axis](Item& a, Item& b) {return a[axis] != b[axis] ? a[axis] > b[axis] : a[!axis] < b[!axis]; });
		for (int i = 0, cur_x = n; i < n; i++, cur_x--)
			if (items[i][axis] <= cur_x)
			{
				for (int j = 0; j < abs(items[i][axis] - cur_x); j++)
					Move(items[i].idx, axis == 0 ? 'D' : 'R');
				items[i][axis] = cur_x;
			}
	}

	cout << ans.size() << '\n';
	for (auto& a : ans) cout << a.first << ' ' << a.second << '\n';
}