[백준/c++] 배열 돌리기 4

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

구현해야할 조건

2사 분면이랑 4사분면의 위치가 가운데에서 만나면 이동이 끝나는 것으로 짰다. 이게 다른 블로그에서 알고리즘을 배운것인데,,, 어딘지 정확히 기억이 안나서 못찾겠다.. 그분에게 감사합니다. 그리고 next_permutation에서 조합을 구해서 문제를 해결하는 것인데 DFS로 굳이 길게 만들지 않아도 괜찮다 왜냐면 최대가 6개 이기 때문에!

code

#include<iostream> 
#include<algorithm>
#include<vector>
#include<cstring>

#define MAX 51
using namespace std;

struct contents{
	int y;
	int x;
	int s;
}content[7];

int n,m,k;
int board[MAX][MAX];
int copyBoard[MAX][MAX];

void solve(int order)
{
	int y = content[order].y;
	int x = content[order].x;
	int s = content[order].s;
	
	int y1 = y - s - 1;
	int x1 = x - s - 1;
	
	int y2 = y - s - 1;
	int x2 = x + s - 1;
	
	int y3 = y + s - 1;
	int x3 = x - s - 1;
	
	int y4 = y + s - 1;
	int x4 = x + s - 1;
	
	while(y1 < y4)
	{
		int temp = copyBoard[y1][x1];
		
		for(int i = y1; i < y3; i++)
		{
			copyBoard[i][x1] = copyBoard[i+1][x1];
		}
		
		for(int i = x3; i < x4; i++)
		{
			copyBoard[y3][i] = copyBoard[y3][i+1];
		}
		for(int i = y4; i > y2; i--)
		{
			copyBoard[i][x2] = copyBoard[i-1][x2];
		}
		for(int i = x2; i > x1; i--)
		{
			copyBoard[y1][i] = copyBoard[y1][i-1];
		}
		
		copyBoard[y1][x1+1] = temp; // 배열 이동 방법!!
		
		y1 += 1;
		x1 += 1;
		
		y2 += 1;
		x2 -= 1;
		
		y3 -= 1;
		x3 += 1;
		
		y4 -= 1;
		x4 -= 1;
	}
}



int main()
{
	cin >> n >> m >> k;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}
	
	vector<int> v;
	
	for(int i = 1; i <= k; i++)
	{
		cin >> content[i].y >> content[i].x >> content[i].s;
		v.push_back(i);
	}
	
	int ans = 987654321;
	
	do{
		
		memset(copyBoard,0,sizeof(copyBoard));
		memcpy(copyBoard,board,sizeof(copyBoard));
		
		for(int i = 0; i < v.size(); i++)
			solve(v[i]);
			
		for(int i = 0; i < n; i++)
		{
			int compare = 0;
			
			for(int j = 0; j < m; j++)
			{
				compare += copyBoard[i][j];
			}
			ans = min(ans,compare);
		}
		
	}while(next_permutation(v.begin(),v.end()));
	
	cout << ans;
	
	return 0;
	
}