[BOJ] 17406: 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

말 그대로 배열을 돌린다.

가능한 회전 연산의 수는 최대 6가지이니 O(K!)에서 6! = 720

회전은 구현하기는 복잡해 보여도 시간 복잡도가 크진 않으니 무식한 방법으로 1초 안에 풀 수 있겠다.

 

 

배열 자체를 복사해도 딱히 타임아웃이 나지는 않는다.

값 형식으로 전달하면 코드도 깔끔해지고 어차피 배열을 다시 바꾸려면 벡터를 만들어야 하기에 그 방법으로 바꿨다.

 

K의 값이 최대 6인 만큼 무식하게 풀어도 상관 없기에

배열의 회전을 구현하는 것이 관건인 문제다.

 

 

다음과 같은 배열에 (3, 4, 2)연산을 적용하려고 할 때, 중심은 당연 3행 4열인 A[3][4](실제 코드에서는 A[2][3])이 될 것이다. 이 중심은 움직이지 않는다.

 

그림을 통해 회전 연산을 할 배열은 한 변의 길이가 2 * s + 1인 정사각형의 모습을 한다는 것을 알 수 있다.

 

for (int ns = 1; ns <= s; ++ns) {
		std::vector<int> group;
		for (int nr = r - ns, nc = c - ns; nc < c + ns; ++nc) {
			group.push_back(a[nr][nc]);
		}
		for (int nr = r - ns, nc = c + ns; nr < r + ns; ++nr) {
			group.push_back(a[nr][nc]);
		}
		for (int nr = r + ns, nc = c + ns; nc > c - ns; --nc) {
			group.push_back(a[nr][nc]);
		}
		for (int nr = r + ns, nc = c - ns; nr > r - ns; --nr) {
			group.push_back(a[nr][nc]);
		}
		groups.push_back(group);
	}

 

그리고 먼저, 1부터 s까지 증가하는 변수 ns를 만든다.

회전 연산을 적용해야 할 요소들은 각각 [2 * 1 + 1, 2 * s +1]의 범위를 갖는 정사각형의 테두리로 나타내진다.

 

반복문을 통해 정사각형의 가장자리만 저장한다.

 

1 2 3

8 9 4

7 6 5

 

와 같은 형태의 배열이였다면, { 1, 2, 3, 4, 5, 6, 7, 8 }으로 벡터에 저장되었을 것이다.

 

for (int ns = 1; ns <= s; ++ns) {
    auto& group = groups[ns - 1];
    std::rotate(group.rbegin(), group.rbegin() + 1, group.rend());
    // ...
}

 

여기에 각각 rotate 함수를 사용한다.

rotate 함수에 대해선 라이님 블로그에 잘 정리되어 있다 (kks227.blog.me/220246910224)

[C++ 강좌] 095 - 알고리즘 헤더 파일 (4) - reverse(), rotate(), random_shuffle()

for (int ns = 1; ns <= s; ++ns) {
    // rotate 연산 적용 ...
    
    int len = group.size();
    int index = 0;
    for (int nr = r - ns, nc = c - ns; nc < c + ns; ++nc) {
        a[nr][nc] = group[index++];
    }
    for (int nr = r - ns, nc = c + ns; nr < r + ns; ++nr) {
        a[nr][nc] = group[index++];
    }
    for (int nr = r + ns, nc = c + ns; nc > c - ns; --nc) {
        a[nr][nc] = group[index++];
    }
    for (int nr = r + ns, nc = c - ns; nr > r - ns; --nr) {
        a[nr][nc] = group[index++];
    }
}

 

위 벡터에 rotate 연산을 적용한 결과는 다음과 같을 것이다.

{ 8, 1, 2, 3, 4, 5, 6, 7 }

 

이제 이 바뀐 값을 아까 정사각형의 가장자리에 넣어 주면 끝이다.

 

8 1 2

7 9 3

6 5 4

 

배열을 성공적으로 회전시켰다.

ns가 증가하며 다른 정사각형들에도 똑같이 연산이 적용 될 것이다.

 

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>

int N, M, K;
std::vector<std::vector<int>> A;

int getMinValue(std::vector<std::vector<int>>& a) {
	int ret = 10e8;
	for (int i = 0; i < N; ++i) {
		int sum = 0;
		for (int j = 0; j < M; ++j) {
			sum += a[i][j];
		}
		ret = std::min(ret, sum);
	}
	return ret;
}

void solve(std::vector<std::vector<int>>& a, std::tuple<int, int, int> t) {
	int r, c, s;
	std::tie(r, c, s) = t;
	std::vector<std::vector<int>> groups;
	for (int ns = 1; ns <= s; ++ns) {
		std::vector<int> group;
		for (int nr = r - ns, nc = c - ns; nc < c + ns; ++nc) {
			group.push_back(a[nr][nc]);
		}
		for (int nr = r - ns, nc = c + ns; nr < r + ns; ++nr) {
			group.push_back(a[nr][nc]);
		}
		for (int nr = r + ns, nc = c + ns; nc > c - ns; --nc) {
			group.push_back(a[nr][nc]);
		}
		for (int nr = r + ns, nc = c - ns; nr > r - ns; --nr) {
			group.push_back(a[nr][nc]);
		}
		groups.push_back(group);
	}
	for (int ns = 1; ns <= s; ++ns) {
		auto& group = groups[ns - 1];
		std::rotate(group.rbegin(), group.rbegin() + 1, group.rend());
		int len = group.size();
		int index = 0;
		for (int nr = r - ns, nc = c - ns; nc < c + ns; ++nc) {
			a[nr][nc] = group[index++];
		}
		for (int nr = r - ns, nc = c + ns; nr < r + ns; ++nr) {
			a[nr][nc] = group[index++];
		}
		for (int nr = r + ns, nc = c + ns; nc > c - ns; --nc) {
			a[nr][nc] = group[index++];
		}
		for (int nr = r + ns, nc = c - ns; nr > r - ns; --nr) {
			a[nr][nc] = group[index++];
		}
	}
}

int main() {
	std::cin >> N >> M >> K;
	A.resize(N);
	for (int i = 0; i < N; ++i) {
		A[i].resize(M);
		for (int j = 0; j < M; ++j) {
			std::cin >> A[i][j];
		}
	}

	std::vector<std::tuple<int, int, int>> rotateVec;
	for (int i = 0; i < K; ++i) {
		int r, c, s;
		std::cin >> r >> c >> s;
		--r; --c;
		rotateVec.push_back({ r, c, s });
	}
	std::sort(rotateVec.begin(), rotateVec.end());
	int ret = 10e8;
	do {
		auto a = A;
		for (const auto& tuple : rotateVec) {
			solve(a, tuple);
		}
		ret = std::min(ret, getMinValue(a));
	} while (std::next_permutation(rotateVec.begin(), rotateVec.end()));
	std::cout << ret;

	return 0;
}