3043 - 장난감 탱크

step 1

행과 열을 분리해서 볼 수 있습니다.

step 2

$N$ * $N$ 크기에 $N$개의 탱크를 놓습니다. 어떤 행이나 열에도 2개 이상의 탱크가 놓일 수 없으니 결국 모든 행에 1대, 모든 열에 1대의 탱크가 놓입니다.

열을 먼저 생각해 봅시다. 처음에 탱크가 배치되어 있고 이 탱크들을 모든 열에 1대씩 있도록 재배치해야 합니다.처음 배치에서 두 탱크를 고른다고 생각해 봅시다. 왼쪽에 있는 탱크를 $X$, 오른쪽에 있는 탱크를 $Y$라고 합시다. 이 두 탱크는 재배치된 이후에도 $X$가 $Y$ 왼쪽에 있어야 합니다. 이것을 잘 생각해 보면 열을 기준으로 정렬한 뒤 제일 왼쪽에 있는 탱크는 1번째 열, 두번째로 왼쪽에 있는 탱크는 2번째 열, ..., $N$번째로 왼쪽에 있는 탱크는 $N$번째 열에 있어야 함을 알 수 있습니다. 행도 마찬가지로 하면 됩니다.

코드

#include<stdio.h>
#include<algorithm>
using namespace std;
struct data {
	int x, y;
	inline bool operator<(const data &temp)const {
		return x < temp.x;
	}
}b1[1000],b2[1000];
int main() {
	int n, j,i,x,y;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d %d", &x, &y);
		b1[i].x = x;
		b1[i].y = i;
		b2[i].x = y;
		b2[i].y = i;
	}
	sort(b1 + 1, b1 + n + 1);
	sort(b2 + 1, b2 + n + 1);
	int cnt = 0;
	for (i = 1; i <= n; i++) {
		if (b1[i].x > i) {
			for (j = i; j <= b1[i].x - 1; j++) cnt++;
		}
		if (b1[i].x < i) {
			for (j = b1[i].x; j <= i - 1; j++) cnt++;
		}
	}
	for (i = 1; i <= n; i++) {
		if (b2[i].x > i) {
			for (j = i; j <= b2[i].x - 1; j++) cnt++;
		}
		if (b2[i].x < i) {
			for (j = b2[i].x; j <= i - 1; j++) cnt++;
		}
	}
	printf("%d\n", cnt);
	for (i = 1; i <= n; i++) {
		if (b1[i].x > i) {
			for (j = i; j <= b1[i].x-1; j++) printf("%d U\n", b1[i].y);
		}
	}
	for (i = n; i >= 1; i--) {
		if (b1[i].x < i) {
			for (j = b1[i].x; j <= i - 1; j++) printf("%d D\n", b1[i].y);
		}
	}
	for (i = 1; i <= n; i++) {
		if (b2[i].x > i) {
			for (j = i; j <= b2[i].x-1; j++) printf("%d L\n", b2[i].y);
		}
	}
	for (i = n; i >= 1; i--) {
		if (b2[i].x < i) {
			for (j = b2[i].x; j <= i - 1; j++) printf("%d R\n", b2[i].y);
		}
	}
	return 0;
}