[C++] 응원단 (백준 28300번)
https://www.acmicpc.net/problem/28300
우선 이 문제의 포인트는 행이동/열이동과 스왑 연산을 분리하여 각각 처리해주는 것이다.
스왑 연산은 어떤 수와 어떤 수를 스왑하는지만 잘 저장해둔다면 어느 순서에서 하든 상관없기 때문에, 일단 무시하고 마지막에 한번에 처리해주도록 하자.
그렇다면 지금은 행이동/열이동만 순서대로 보면서 처리해주겠다. 이것들은 순서가 중요하기 때문에 한번에 모아서 처리하거나 하기 어렵다. 그렇다고 n*n 배열에서 실제로 행이동과 열이동을 매번 시켜주면 많은 시간이 걸릴 것이다.
잘 생각해보면 이렇게 행이동/열이동으로는 저 4개의 수끼리의 위치는 절대 바뀔 수 없다. 행이동과 열이동은 무조건 짝수 행/열 또는 홀수 행/열에 대해서만 이루어지기 때문이다.
그렇다는 것은 왼쪽 위 4개의 수(초록색 사각형 안에 있는 4개의 수)의 위치만 잘 기록해두면 마지막에 행이동/열이동이 모두 끝난 후에 나머지 수들도 채워줄 수 있다는 것이다. 행이동과 열이동은 이렇게 처리하면 된다.
이제 남은 건 스왑 연산이다. 다시 리마인드하자면, 스왑 연산은 중간 중간에 있을 수 있지만 우리는 잘 기록해두었다가 맨 마지막에 몰아서 처리하려고 하는 것이다.
스왑 연산이 원래부터 맨 마지막에 있었다면? 그냥 스왑해주면 된다.
그런데 스왑 연산이 중간에 있었다면? 그 이후에 있었던 행이동/열이동을 반영하여 스왑해주어야 하는 것이다.
즉, 해당 스왑 연산을 마지막 단계에서 잘 처리해주려면 해당 스왑 연산 이후에 행이동과 열이동이 어떻게 이루어졌는지만 잘 기록해두면 되는 것이다.
이를 위해서는 역추적을 하면 된다. 뒤에서부터 보면서 행이동과 열이동이 어떻게 이루어졌는지 기록하다가 스왑 연산을 만나면 지금까지 기록해뒀던 행이동/열이동 연산들을 반영해서 스왑 연산을 수정해준다. 맨 앞에 도달하면 다시 내가 수정해서 저장해둔 스왑 연산들을 읽으면서 그대로 스왑해주면 된다.
행이동/열이동 연산들을 기록할 때는, 홀수행+홀수열 원소, 홀수행+짝수열 원소, 짝수행+홀수열 원소, 짝수행+짝수열 원소로 나누어서 각각의 이동량을 누적해주면 된다. 주의할 점은 마지막에 수정한 스왑 연산들을 처리해줄 때는 다시 앞에서부터 읽으면서 스왑해주어야 한다는 점이다.
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector<pair<int, int>> a(4);
vector<tuple<string, int, int, int, int>> query;
// 4개의 원소가 각 행이동과 열이동으로 어느 위치로 갔는지 기록
// 쿼리도 전부 저장해둠 (이따가 역추적 시 사용)
a[0] = make_pair(1, 1);
a[1] = make_pair(1, 2);
a[2] = make_pair(2, 1);
a[3] = make_pair(2, 2);
for (int i = 0; i < q; i++) {
string op;
cin >> op;
if (op == "RO") {
for (int i = 0; i < 4; i++) {
if (a[i].first % 2 == 1) a[i].second = a[i].second % n + 1;
}
query.push_back({op, 0, 0, 0, 0});
} else if (op == "RE") {
for (int i = 0; i < 4; i++) {
if (a[i].first % 2 == 0) a[i].second = a[i].second % n + 1;
}
query.push_back({op, 0, 0, 0, 0});
} else if (op == "CO") {
for (int i = 0; i < 4; i++) {
if (a[i].second % 2 == 1) a[i].first = a[i].first % n + 1;
}
query.push_back({op, 0, 0, 0, 0});
} else if (op == "CE") {
for (int i = 0; i < 4; i++) {
if (a[i].second % 2 == 0) a[i].first = a[i].first % n + 1;
}
query.push_back({op, 0, 0, 0, 0});
} else if (op == "S") {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
query.push_back({op, r1, c1, r2, c2});
}
}
// 4개의 원소의 위치를 통해 다른 원소들의 위치도 결정
vector<vector<int>> ans(n + 1, vector<int>(n + 1, -1));
for (int i = 0; i < n; i += 2) {
for (int j = 0; j < n; j += 2) {
ans[(a[0].first + i - 1) % n + 1][(a[0].second + j - 1) % n + 1] = n * i + 1 + j;
}
}
for (int i = 0; i < n; i += 2) {
for (int j = 0; j < n; j += 2) {
ans[(a[1].first + i - 1) % n + 1][(a[1].second + j - 1) % n + 1] = n * i + 2 + j;
}
}
for (int i = 0; i < n; i += 2) {
for (int j = 0; j < n; j += 2) {
ans[(a[2].first + i - 1) % n + 1][(a[2].second + j - 1) % n + 1] = n * i + n + 1 + j;
}
}
for (int i = 0; i < n; i += 2) {
for (int j = 0; j < n; j += 2) {
ans[(a[3].first + i - 1) % n + 1][(a[3].second + j - 1) % n + 1] = n * i + n + 2 + j;
}
}
// 역추적하면서 각 스왑 연산 이후에 어떻게 원소들이 이동했는지 파악해서 스왑에 저장해둠
vector<pair<int, int>> pos(4); // <행 이동량, 열 이동량>
vector<tuple<int, int, int, int>> swaps;
pos[0] = {0, 0}; // OO
pos[1] = {0, 0}; // OE
pos[2] = {0, 0}; // EO
pos[3] = {0, 0}; // EE
for (int i = q - 1; i >= 0; i--) {
auto [op, x1, y1, x2, y2] = query[i];
if (op == "RO") {
pos[0].second++;
pos[1].second++;
swap(pos[0], pos[1]); // 홀짝이 바뀌었으니 swap까지 해주기
} else if (op == "RE") {
pos[2].second++;
pos[3].second++;
swap(pos[2], pos[3]); // 홀짝이 바뀌었으니 swap까지 해주기
} else if (op == "CO") {
pos[0].first++;
pos[2].first++;
swap(pos[0], pos[2]); // 홀짝이 바뀌었으니 swap까지 해주기
} else if (op == "CE") {
pos[1].first++;
pos[3].first++;
swap(pos[1], pos[3]); // 홀짝이 바뀌었으니 swap까지 해주기
} else if (op == "S") {
// 현재 스왑 연산 이후에 있던 연산들 모두 반영해서 swaps에 넣어주기
// (x1, y1) 계산
if (x1 % 2 == 1 && y1 % 2 == 1) { // OO
x1 = (x1 + pos[0].first - 1) % n + 1;
y1 = (y1 + pos[0].second - 1) % n + 1;
} else if (x1 % 2 == 1 && y1 % 2 == 0) { // OE
x1 = (x1 + pos[1].first - 1) % n + 1;
y1 = (y1 + pos[1].second - 1) % n + 1;
} else if (x1 % 2 == 0 && y1 % 2 == 1) { // EO
x1 = (x1 + pos[2].first - 1) % n + 1;
y1 = (y1 + pos[2].second - 1) % n + 1;
} else if (x1 % 2 == 0 && y1 % 2 == 0) { // EE
x1 = (x1 + pos[3].first - 1) % n + 1;
y1 = (y1 + pos[3].second - 1) % n + 1;
}
// (x2, y2) 계산
if (x2 % 2 == 1 && y2 % 2 == 1) { // OO
x2 = (x2 + pos[0].first - 1) % n + 1;
y2 = (y2 + pos[0].second - 1) % n + 1;
} else if (x2 % 2 == 1 && y2 % 2 == 0) { // OE
x2 = (x2 + pos[1].first - 1) % n + 1;
y2 = (y2 + pos[1].second - 1) % n + 1;
} else if (x2 % 2 == 0 && y2 % 2 == 1) { // EO
x2 = (x2 + pos[2].first - 1) % n + 1;
y2 = (y2 + pos[2].second - 1) % n + 1;
} else if (x2 % 2 == 0 && y2 % 2 == 0) { // EE
x2 = (x2 + pos[3].first - 1) % n + 1;
y2 = (y2 + pos[3].second - 1) % n + 1;
}
// swaps에 넣어주기
swaps.push_back({x1, y1, x2, y2});
}
}
// 아까 계산해둔대로 실제로 스왑해주기
int sn = swaps.size();
for (int i = sn - 1; i >= 0; i--) {
auto [x1, y1, x2, y2] = swaps[i];
swap(ans[x1][y1], ans[x2][y2]);
}
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < n + 1; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}(AC)