[BOJ]17406번: 배열 돌리기 4 (c++)

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

구현 + 브루트포스

//https://www.acmicpc.net/problem/17406
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

template <typename T>
using d_vector = vector<vector<T>>;

// r, c : 회전하는 사각형의 가장 왼쪽 윗칸
struct rtt_info 
{
	int r, c, s;
};

int get_min_sum_array(d_vector<int> &A)
{
	int min_sum = numeric_limits<int>::max();
	for (int i = 0; i < A.size(); ++i)
	{
		int sum = 0;
		for (int j = 0; j < A[i].size(); ++j)
		{
			sum += A[i][j];
		}
		min_sum = min(sum, min_sum);
	}
	return min_sum;
}

void inline swap(int &val1, int &val2)
{
	int tmp = val1;
	val1 = val2;
	val2 = tmp;
}

void move_val(d_vector<int>& A, rtt_info info)
{
	int len = info.s * 2;
	int bf_val = A[info.r][info.c];

	// 윗변을 오른쪽으로 한칸씩 이동
	for (int i = 0; i < len; ++i)
	{
		swap(A[info.r][++info.c], bf_val);
	}
	// 우변을 아래쪽으로 한칸씩 이동
	for (int i = 0; i < len; ++i)
	{
		swap(A[++info.r][info.c], bf_val);
	}
	// 밑변을 왼쪽으로 한칸씩 이동
	for (int i = 0; i < len; ++i)
	{
		swap(A[info.r][--info.c], bf_val);
	}
	// 좌변을 위쪽으로 한칸씩 이동
	for (int i = 0; i < len; ++i)
	{
		swap(A[--info.r][info.c], bf_val);
	}
}

void rotate(d_vector<int>& A, rtt_info info)
{
	// info.s > 0 일 동안 회전
	while (info.s)
	{
		// 네 변의 값들을 한칸씩 이동
		move_val(A, info);

		// (더 작은) 다음 회전사각형 준비
		++info.r;
		++info.c;
		--info.s;
	}
}

int get_min_sum_rotated_2d_vector(d_vector<int> A, vector<rtt_info> &infos, vector<int> &order)
{
	// 배열 A회전 : order순서에 따른 info값 대로
	for (int idx : order)
	{
		rotate(A, infos[idx]);
	}
	
	// 회전 후 배열 A의 최솟값 반환
	return get_min_sum_array(A);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N, M, K;
	cin >> N >> M >> K;
	d_vector<int> A(N, vector<int>(M));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> A[i][j];
		}
	}
	vector<rtt_info> infos(K);
	for (int i = 0; i < K; ++i)
	{
		int R, C, S;
		cin >> R >> C >> S;

		infos[i].r = R - S - 1;
		infos[i].c = C - S - 1;
		infos[i].s = S;
	}

	// 순열을 위한 order배열 생성
	vector<int> order(K);
	for (int i = 0; i < K; ++i)
	{
		order[i] = i;
	}
	
	// infos 순열대로 배열A를 회전시키고 최솟값 구하기
	int min_val = numeric_limits<int>::max();
	do {
		
		int val = get_min_sum_rotated_2d_vector(A, infos, order);
		min_val = min(min_val, val);

	} while (next_permutation(order.begin(), order.end()));

	// 출력
	cout << min_val;

	return 0;
}

 

이 문제는 구현적 성격이 강했다.

 

TIP_순열

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

1 ≤ K ≤ 6

 

회전의 순서에 따라 값이 달라지고, 그 값들의 최솟값을 구해야 한다.

이때 회전 정보의 개수가 K로 주어지는데, 이 값의 크기가 매우 작다.

따라서 순열로 하나하나 값을 구해서 크기를 비교하는 것이 적절하다.

 

 

 

TIP_회전

과정을 하나씩 쪼개서 생각하는게 좋다.

 

1. vector<info> infos 순서대로 회전

// 배열 A회전 : order순서에 따른 info값 대로
for (int idx : order)
{
	rotate(A, infos[idx]);
}

 

2. 한 사각형에는 info.s 크기만큼 내부 사각형이 있다.

내부 사각형들의 시작점은 우하향한다. 

// info.s > 0 일 동안 회전
while (info.s)
{
	// 네 변의 값들을 한칸씩 이동
	move_val(A, info);

	// (더 작은) 다음 회전사각형 준비
	++info.r;
	++info.c;
	--info.s;
}

 

3. 4변의 값을 한칸씩 이동.

이전 칸의 값을 bf_val 변수를 두어서 다음 이동으로 넘긴다.

int len = info.s * 2;
int bf_val = A[info.r][info.c];

// 윗변을 오른쪽으로 한칸씩 이동
for (int i = 0; i < len; ++i)
{
	swap(A[info.r][++info.c], bf_val);
}

...