백준 17406 배열돌리기4 문제 풀이

 

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

17406번: 배열 돌리기 4

백준저지 17406번 문제 배열 돌리기4 문제 풀이입니다.

 

K가 6밖에 안되므로, 6개를 줄세우는 가짓수는 6!=720개 뿐입니다.

 

따라서 완전탐색을 하면 되는 구현위주의 문제입니다.

 

Rotation시키는 것은, 돌아가는 원판에 있는 숫자들을 다 저장해놓고, 한칸씩 더 이동시켜서 다시 넣는 방식으로 했으며

 

왼쪽위 오른쪽위, 오른쪽아래, 왼쪽아래 꼭지점을 기준으로

 

해당 꼭지점에 다다를때 이동방향을 바꾸는 식으로 구현해보았습니다.

 

 

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

typedef pair<int, int> pii;
int A[55][55];
typedef struct _Rot {
	int r, c, s;
} Rot;
Rot rot[10];
int N, M, K;
int ans;
void get_input();
bool used[10];
int order[10];
void copy(int A[][55], int B[][55]);
const int dx[] = { +0, +1, +0, -1 };
const int dy[] = { +1, +0, -1, +0 };

void _rotate(int B[][55], int row, int col, int rad) {
	vector<int> val;
	int x = row - rad;
	int y = col - rad;
	int cnt = rad * 8;
	set<pii> check;
	check.insert(make_pair(row + rad, col + rad));
	check.insert(make_pair(row - rad, col + rad));
	check.insert(make_pair(row + rad, col - rad));
	int k = 0;
	for (int i = 0; i < cnt; i++) {
		val.push_back(B[x][y]);
		x += dx[k];
		y += dy[k];
		if (check.find(make_pair(x, y)) != check.end()) {
			k++;
		}
	}
	k = 0;
	x = row - rad;
	y = col - rad;
	x += dx[0];
	y += dy[0];
	for (int i = 0; i < cnt; i++) {
		B[x][y] = val[i];
		x += dx[k];
		y += dy[k];
		if (check.find(make_pair(x, y)) != check.end()) {
			k++;
		}
	}
}
void rotate(int B[][55], int row, int col, int rad) {
	for (int i = 1; i <= rad; i++) {
		_rotate(B, row - 1, col - 1, i);
	}
}
void dfs(int p) {
	if (p < K) {
		for (int i = 0; i < K; i++) {
			if (used[i] == false) {
				used[i] = true;
				order[p] = i;
				dfs(p + 1);
				used[i] = false;
			}
		}
	}
	else {
		//do simulation
		int B[55][55];
		copy(B, A);
		for (int i = 0; i < K; i++) {
			auto& o = rot[order[i]];
			rotate(B, o.r, o.c, o.s);
		}
		
		for (int i = 0; i < N; i++) {
			int sum = 0;
			for (int j = 0; j < M; j++) {
				sum += B[i][j];
			}
			ans = min(ans, sum);
		}

		
	}
}
int main() {
	ans = 987654321;
	get_input();
	dfs(0);
	cout << ans << endl;
}

void get_input() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++) 
			cin >> A[i][j];
		
	for (int i = 0; i < K; i++) {
		auto& R = rot[i];
		cin >> R.r >> R.c >> R.s;
	}
}
void copy(int A[][55], int B[][55]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			A[i][j] = B[i][j];
		}
}