[BOJ 3043 // C++] 장난감 탱크

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3043번 문제인 장난감 탱크이다.
문제는 아래 링크를 확인하자.

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

3043번: 장난감 탱크

주어진 N개의 장난감 탱크를 최소횟수로 움직여 모든 행과 모든 열에 정확히 하나의 탱크가 있게 하는 문제이다.

 

각 탱크를 행번호 오름차순으로 살펴보면 각 탱크들을 몇 행으로 보내야 행방향 이동을 최소화할 수 있는지를 알 수 있고, 이는 열에 대해서도 마찬가지이다. 이로부터 구할 수 있는 각 탱크들이 도착해야 할 행과 열로 탱크를 이동시켜야 할 것이다. 다만 문제 조건에 따라 이 이동과정에서 서로 다른 두 탱크가 같은 칸을 차지하는 일이 벌어지면 안되므로 어떻게 이러한 상황을 막을 수 있을지를 생각해보자.

 

어떤 탱크를 아래 행의 칸으로 옮겨야하는데 그 칸에 탱크가 있는 상황을 생각해보자. 움직이고자 하는 탱크가 아래행으로 이동해야하는 탱크라는 것은 현재 아래 행에 있는 탱크의 목표 행 또한 그보다 더 아래의 행이어야 함을 의미한다. 따라서 이러한 상황이 있을 경우 아래 행의 탱크를 먼저 아래로 움직여주는 것으로 상황을 해결할 수 있다. 물론 이 아래행의 탱크 또한 그 아래 행에 탱크가 있을 수 있으므로, 글쓴이는 이러한 움직임을 함수를 통해 재귀적으로 구현해주었다.

 

위 문단의 서술은 다른 방향의 이동에도 똑같이 적용할 수 있다. 이를 이용해 문제를 해결해주자.

 

아래는 제출한 소스코드이다.

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

int N;
int arr[500];
int R[501], C[501];
int board[501][501];

vector<pair<int, char>> ans;

void moveup(int idx, int& pos) {
	int r = R[idx], c = C[idx];
	if (board[r - 1][c]) moveup(board[r - 1][c], R[board[r - 1][c]]);
	board[r - 1][c] = board[r][c];
	board[r][c] = 0;
	pos--;
	ans.emplace_back(make_pair(idx, 'U'));
}

void movedown(int idx, int& pos) {
	int r = R[idx], c = C[idx];
	if (board[r + 1][c]) movedown(board[r + 1][c], R[board[r + 1][c]]);
	board[r + 1][c] = board[r][c];
	board[r][c] = 0;
	pos++;
	ans.emplace_back(make_pair(idx, 'D'));
}

void moveleft(int idx, int& pos) {
	int r = R[idx], c = C[idx];
	if (board[r][c - 1]) moveleft(board[r][c - 1], C[board[r][c - 1]]);
	board[r][c - 1] = board[r][c];
	board[r][c] = 0;
	pos--;
	ans.emplace_back(make_pair(idx, 'L'));
}

void moveright(int idx, int& pos) {
	int r = R[idx], c = C[idx];
	if (board[r][c + 1]) moveright(board[r][c + 1], C[board[r][c + 1]]);
	board[r][c + 1] = board[r][c];
	board[r][c] = 0;
	pos++;
	ans.emplace_back(make_pair(idx, 'R'));
}

bool compR(int& x, int& y) {
	return R[x] < R[y];
}

bool compC(int& x, int& y) {
	return C[x] < C[y];
}

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

	cin >> N;

	for (int i = 1; i <= N; i++) {
		int& r = R[i], &c = C[i]; cin >> r >> c;
		board[r][c] = i;
	}
	for (int i = 0; i < N; i++) arr[i] = i + 1;

	sort(arr, arr + N, compR);
	for (int i = 0; i < N; i++) {
		int idx = arr[i], tar = i + 1;
		int& pos = R[idx];
		while (pos > tar) moveup(idx, pos);
		while (pos < tar) movedown(idx, pos);
	}

	sort(arr, arr + N, compC);
	for (int i = 0; i < N; i++) {
		int idx = arr[i], tar = i + 1;
		int& pos = C[idx];
		while (pos > tar) moveleft(idx, pos);
		while (pos < tar) moveright(idx, pos);
	}

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