[백준][C++] 17406: 배열 돌리기 4

문제 링크: https://www.acmicpc.net/problem/17406

 

브루트포스 문제입니다.

배열이 주어지고, 회전 연산 k개가 주어집니다. 배열의 값 = 배열 한 행의 합 중에서 최소값인데 회전 연산의 순서를 요리조리 바꿨을 때 배열의 값 중 최소값을 구하는 문제입니다.

 

순열 만드는건 어렵지 않습니다. 회전 연산을 정렬시킨 다음 std::next_permutation을 사용하면 됩니다.

문제는 회전인데.. 생각해보니까 위 사진처럼 한 원소를 잡고 반시계방향으로 계속 swap하면서 원래 위치 직전까지 한개씩 swap 하면 시계방향으로 한칸씩 회전시킨 것과 같아집니다.

이런식으로 풀면 됩니다 

#include <bits/stdc++.h>
using namespace std;


int arr_org[50][50];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, -1, 0, 1};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> arr_org[i][j];

	int mn = 1e9;
	vector<tuple<int, int, int>> ops(k);
	for (auto& [r, c, s] : ops) {
		cin >> r >> c >> s;
		--r, --c;
	}
	sort(ops.begin(), ops.end());

	do {
		int arr[50][50];
		memcpy(arr, arr_org, sizeof(arr_org));

		for (const auto& [r, c, s] : ops) {
			for (int i = s; i > 0; --i) {
				int curr_y = r + i;
				int curr_x = c + i;

				for (int j = 0; j < 4; ++j) {	//dir
					for (int k = 0; k < 2 * i; ++k) {
						if (j == 3 && k == 2 * i - 1) break;

						int next_y = curr_y + dy[j];
						int next_x = curr_x + dx[j];

						swap(arr[curr_y][curr_x], arr[next_y][next_x]);

						curr_y = next_y;
						curr_x = next_x;
					}
				}
			}
		}

		for (int i = 0; i < n; ++i)
			mn = min(mn, accumulate(arr[i], arr[i]+m, 0));
	} while (next_permutation(ops.begin(), ops.end()));

	cout << mn << '\n';

	return 0;
}