[백준/BOJ] 백준 17406번 : 배열 돌리기 4

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

회전 연산들을 정렬 후, next_permutation을 통해 회전 연산의 순서를 바꿔가며 문제를 해결한다.

 

코드

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

int n, m, k;

int board[51][51];
int temp_board[51][51];

void turn(int r, int c, int s)
{
	//이부분들은 당기다 보면 빠져 나오는 값들이므로 미리 저장해 놓는다
	int left_up = board[r - s][c - s];
	int right_up = board[r - s][c + s];
	int right_down = board[r + s][c + s];
	int left_down = board[r + s][c - s];


	//왼쪽 위로 1칸씩 당기기
	for (int i = 0; i < s * 2; i++)
	{
		board[r - s + i][c - s] = board[r - s + i + 1][c - s];
	}

	//아래쪽 왼쪽으로 1칸씩 당기기
	for (int i = 0; i < s * 2; i++)
	{
		board[r + s][c - s + i] = board[r + s][c - s + i + 1];
	}

	//오른쪽 아래로 1칸씩 당기기
	for (int i = 0; i < s * 2; i++)
	{
		board[r + s - i][c + s] = board[r + s - i - 1][c + s];
	}

	//위쪽 오른쪽으로 1칸식 당기기
	for (int i = 0; i < s * 2; i++)
	{
		board[r - s][c + s - i] = board[r - s][c + s - i - 1];
	}

	//당겨서 빠져 나온 칸 넣기
	board[r - s][c - s + 1] = left_up;
	board[r + s - 1][c - s] = left_down;
	board[r + s][c + s - 1] = right_down;
	board[r - s + 1][c + s] = right_up;
}

//회전연산을 시행한다
void turnSolve(int r, int c, int s)
{
	//안쪽부터 바깥쪽으로 회전을 실행한다
	for (int i = 1; i <= s; i++)
	{
		turn(r, c, i);
	}
}

//각 행의 수들의 합중 가장 작은수를 반환한다
int numSolve()
{
	int ret = 987654321;

	for (int i = 1; i <= n; i++)
	{
		int temp = 0;
		for (int j = 1; j <= m; j++)
		{
			temp += board[i][j];
		}
		ret = min(ret, temp);
	}

	return ret;
}

int Solve(vector<pair<pair<int, int>, int>> turn_list)
{
	int ret = 987654321;

	//원본 배열을 미리 저장해 둔다
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			temp_board[i][j] = board[i][j];

	sort(turn_list.begin(), turn_list.end());

	do {

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				board[i][j] = temp_board[i][j];

		for (int i = 0; i < k; i++)
		{
			turnSolve(turn_list[i].first.first, turn_list[i].first.second, turn_list[i].second);
		}

		ret = min(ret, numSolve());

	} while (next_permutation(turn_list.begin(), turn_list.end())); //순열을 통해 회전 연산의 순서를 바꿔간다


	return ret;
}



int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	vector<pair<pair<int, int>, int>> turn_list;

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			int input;

			cin >> input;
			board[i][j] = input;
		}

	for (int i = 0; i < k; i++)
	{
		int r, c, s;

		cin >> r >> c >> s;
		turn_list.push_back(make_pair(make_pair(r, c), s));
	}

	cout << Solve(turn_list);

	return 0;
}