백준 17406 - 배열 돌리기 4

문제링크

• 백준 17406

문제설명

• N x M 크기의 배열이 주어질 때, 해당 배열의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다.
• 배열은 회전 연산을 한다.
  • 세 정수(r, c, s) 가 주어지고, 좌측상단 좌표 (r-s, c-s) 에서 우측상단 좌표(r+s, c+s) 칸까지 해당하는 영역이 회전 영역이 된다.
  • 회전은 바깥 사각형부터 시계방향으로 이루어진다. 즉, 나선형 구조가 아니라 정사각형 형태이다.
  • 가운데 하나의 좌표는 무조건 원래 값 그대로 유지된다.
• 여러 개의 회전 연산이 주어졌을 때, 회전 연산의 순서에 따라 최종 배열의 형태가 달라진다.
• 최종 배열의 최솟값을 찾아라.

문제접근

• DFS를 이용해서 회전 연산의 모든 경우를 찾는다.
  • 하나의 전체 연산 순서가 만들어지면 배열을 회전하고, 최종 배열의 값을 계산한다.
• 회전은 재귀로 구현한다.
  • 회전의 시작점과 회전하는 배열의 길이(2 x s)를 전달해주어 테두리의 원소들을 회전하도록 구현한다.
  • 회전하는 영역의 가운데 위치한 원소는 값을 그대로 유지한다는 점에 주의한다.
• 원래 배열의 값을 항상 가지고 있어야 새로운 연산 순서에도 같은 로직을 적용할 수 있다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

typedef struct _rot {
	int r, c, s;
} Rotate;

int N, M, K;
vector<Rotate> rotList;
vector<int> candRot;
int board[51][51];
int nboard[51][51];
int cboard[51][51];
bool rotated[51][51];
bool visited[6];
int minSum = 9e8;

void rotateArray(int x, int y, int s) {
	if (rotated[x][y]) {
		nboard[x - 1][y - 1] = board[x - 1][y - 1]; // 가운데 부분
		memcpy(board, nboard, sizeof(nboard));
		return;
	}

	int xLimit = x + 2 * s;
	int yLimit = y + 2 * s;

	// 가로줄
	for (int c = y; c <= yLimit; c++) {
		rotated[x][c] = true;
		rotated[xLimit][c] = true;
		if (c == y) {
			nboard[x][c] = board[x + 1][c];
			nboard[xLimit][c] = board[xLimit][c + 1];
		}
		else if(c==yLimit){
			nboard[x][c] = board[x][c - 1];
			nboard[xLimit][c] = board[xLimit - 1][c];
		}
		else {
			nboard[x][c] = board[x][c - 1];
			nboard[xLimit][c] = board[xLimit][c + 1];
		}
	}
	// printBoard();

	// 세로줄
	for (int r = x + 1; r < xLimit; r++) {
		rotated[r][y] = true;
		rotated[r][yLimit] = true;
		nboard[r][y] = board[r + 1][y];
		nboard[r][yLimit] = board[r - 1][yLimit];
	}
	// printBoard();
	rotateArray(x + 1, y + 1, s - 1);
}

void getRowSum() {
	int sum = 0;
	int aSum = 9e8;
	for (int r = 1; r <= N; r++) {
		sum = 0;
		for (int c = 1; c <= M; c++) {
			sum += board[r][c];
		}
		aSum = min(aSum, sum);
	}

	minSum = min(minSum, aSum);
}

void setRotationCand(int v) {
	if (candRot.size() == K) {
		memcpy(board, cboard, sizeof(cboard));
		
		// 회전 로직
		for (auto ele : candRot) {
			memset(rotated, false, sizeof(rotated));
			memcpy(nboard, board, sizeof(board));
			int startX = rotList[ele].r - rotList[ele].s;
			int startY = rotList[ele].c - rotList[ele].s;
			rotateArray(startX, startY, rotList[ele].s);
			// printBoard();
		}
		// printBoard();

		// 회전이 끝난 배열의 값 계산
		getRowSum();
		return;
	}

	for (int i = 0; i < K; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		candRot.push_back(i);
		setRotationCand(i + 1);
		candRot.pop_back();
		visited[i] = false;
	}
}

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

	memset(board, 0, sizeof(board));
	scanf("%d %d %d", &N, &M, &K);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= M; c++) {
			scanf("%d", &board[r][c]);
			cboard[r][c] = board[r][c];
		}
	}

	Rotate rot;
	for (int i = 0; i < K; i++) {
		scanf("%d %d %d", &rot.r, &rot.c, &rot.s);
		rotList.push_back(rot);
	}

	memset(visited, false, sizeof(visited));
	setRotationCand(0);
	printf("%d\n", minSum);
	return 0;
}