[DFS 순열] 백준 17406 배열 돌리기 4 C++

※ 문제

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

17406번: 배열 돌리기 4

 

※ 풀이

1) 회전 연산은 모두 한 번씩 사용해야하며 순서는 바꿔도 상관없으므로 DFS를 이용해 연산 순서 순열을 구한다.

2) DFS로 구한 연산 순서로 최솟값을 구한 후, 배열을 원래대로 바꿔야 다음 연산 순서를 계속해서 진행할 수 있다.

3) 회전 연산은 간격을 1부터 s까지 왼쪽 위부터 반시계 방향으로 회전시킨다.

#include <bits/stdc++.h>

using namespace std;

int n, m, k, ans = INT_MAX;
int arr[52][52], temp[52][52], R[6], C[6], S[6], order[6];
bool visited[6];

void calMin() {
	for (int i = 1; i <= n; i++) {
		int minNum = 0;
		for (int j = 1; j <= m; j++) {
			minNum += arr[i][j];
		}
		ans = min(ans, minNum);
	}
}

void rotate(int r, int c, int s) {
	for (int j = 1; j <= s; j++) {
		int start = arr[r - j][c - j]; // s 아니고 j

		// 반시계
		for (int i = r - j; i < r + j; i++) arr[i][c - j] = arr[i + 1][c - j];
		for (int i = c - j; i < c + j; i++) arr[r + j][i] = arr[r + j][i + 1];
		for (int i = r + j; i > r - j; i--) arr[i][c + j] = arr[i - 1][c + j];
		for (int i = c + j; i > c - j; i--) arr[r - j][i] = arr[r - j][i - 1];

		arr[r - j][c - j + 1] = start;
	}
}

void dfs(int depth) {
	if (depth == k) {
		for (int i = 1; i <= n; i++) { // 배열 임시 저장
			for (int j = 1; j <= m; j++) {
				temp[i][j] = arr[i][j];
			}
		}
		for (int i = 0; i < k; i++) { // 회전
			int idx = order[i];
			rotate(R[idx], C[idx], S[idx]);
		}
		calMin(); // 최솟값 계산
		for (int i = 1; i <= n; i++) { // 배열 원래대로 복원
			for (int j = 1; j <= m; j++) {
				arr[i][j] = temp[i][j];
			}
		}
		return;
	}

	for (int i = 0; i < k; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		order[depth] = i; // 회전 연산 순서
		dfs(depth + 1);
		visited[i] = false;
	}
}

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

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 0; i < k; i++) {
		cin >> R[i] >> C[i] >> S[i];
	}
	
	dfs(0);

	cout << ans;
}