[NYPC 2022 Round 2-A] 로봇 청소기 ★

문제

굉장히 재미있다. 예상 난이도는 플래티넘 2 정도?

고민에서 코딩까지 2시간 걸렸는데.. 이거 괜찮나 ㅋㅋ

 

풀이

기본적인 사항들

• 관찰 1. 많아야 $R$번의 청소를 한다.
• 관찰 2. 청소 경로가 차곡차곡 쌓이는 형태이다.
  • 정확히는, 청소 경로 두 개가 교차할 경우, exchange argument에 의해 꼬인 걸 푸는 게 최적
  • 따라서 청소 경로가 '껍데기처럼 벗겨낼 수 있다' 정도의 이야기

구현 어케하지..

• 생각 1. 수직선을 긋고, 만나는 부분들은 이번에 갖고 가고, 만나지 않는 부분들은 최대한 어케 땡겨서 재귀적으로......??
• 생각 2. 이렇게 밑도 끝도 없이 구현이 막막해진다면 뭔가 단순한 형태로의 변환을 도모해야 한다.
• 생각 3. 격자다. 격자에서 체비셰프 좌표계가 떠오르는 이동들이 있다, 하면 45도 변환이 유용할 때가 많다.
• 관찰 3. 45도 변환한 격자에서 $x$좌표 증가 순으로 스위핑을 한다고 생각해보자. 어떤 점의 아래쪽에 점이 위치한 것은 곧 청소기가 그쪽으로 이동할 수 있다는 의미이다.
• 관찰 4. 새로운 점을 기존의 어떤 점에 연결시킬까에 대한 전략은 [관찰 2]의 exchange argument가 비슷하게 나타난다.
  • 새로운 점의 높이보다 높은 기존의 두 점에 대해서 둘 중 더 낮은 점에 연결하는 것이 exchange argument 상 최적이다.

그리디하게 antichain 관리하기

• 생각 4. [관찰 4]는 곧, set을 이용하여 계단 모양으로 chain을 관리하여 문제를 해결할 수 있다는 생각으로 이어진다.
  • lower_bound와 erase를 잘 사용하면 된다.
• 생각 5. 역추적은 그냥 연결한 점에 대하여 역추적 map 등을 만들어 둠으로써 할 수 있다.
  • 역추적의 점수가 좀 후한데..? ㅋㅋ

 

코드

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) begin(x),end(x)
using vi = vector<int>;
using ii = pair<int,int>;
#define mp make_pair
#define siz(x) int((x).size())
#define fi first
#define se second
#define pb push_back

bool cmp(ii x, ii y){ return mp(x.se,x.fi) < mp(y.se,y.fi); }

int n, m;
vector<ii> v;
set<ii,bool(*)(ii,ii)> s(cmp);
map<ii,ii> from;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	rep(i,1,n) rep(j,1,m) {
		char c; cin >> c;
		if (c == 'X') {
			v.pb({i+j,i-j});
		}
	}
	sort(all(v));

	for (auto e : v) {
		auto it = s.upper_bound(e);
		if (it != begin(s)) {
			from[e] = *prev(it);
			s.erase(prev(it));
		}
		s.insert(e);
	}

	vector<vector<ii>> answer;
	for (auto [x,y] : s) {
		answer.emplace_back();
		while (1) {
			answer.back().emplace_back((x+y)/2,(x-y)/2);
			if (from.count({x,y})) tie(x,y) = from[{x,y}];
			else break;
		}
	}

	cout << siz(answer) << '\n';
	for (auto v : answer) {
		reverse(all(v));
		cout << v[0].se << ' ';
		rep(i,2,v[0].fi) cout << 'D';
		rep(i,1,siz(v)-1) {
			auto [x0,y0] = v[i-1];
			auto [x1,y1] = v[i];
			if (y1 >= y0) {
				rep(j,1,y1-y0) cout << 'R';
				rep(j,1,(x1-x0)-(y1-y0)) cout << 'D';
			} else {
				rep(j,1,y0-y1) cout << 'L';
				rep(j,1,(x1-x0)-(y0-y1)) cout << 'D';
			}
		}
		rep(i,1,n-v.back().fi) cout << 'D';
		cout << '\n';
	}
}

 

아무튼 참 재밌었따!