[BOJ - 17406] 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

 

문제를 똑바로 읽는 습관을 들이도록 하자..

 

이 문제의 가장 중요한 부분은 가장 밑에 두 줄이다...

 

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

 

바로 위에 빨간색으로 표시한 부분인데.. 저 부분을 고려하지 않아서 틀렸었다.

 

이것만 제외하고는 쉬운 문제였다.

 

- 풀이 방법

 

1. 입력을 받는다.

 

2. 회전 연산이 가능한 순열을 구한다(dfs로!!)

 

3. 회전 연산이 가능한 순열의 경우의 수 마다 회전을 해준다.

(회전은 한 칸씩 밀되, 한 번 로테이션이 끝나면 값을 줄여나가면서 안으로 들어가준다.)

 

4. 각 행의 최솟값을 구하고 다음 순열의 회전 연산에 대한 최솟값을 구해준다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

struct CALC {
	int r, c, s;
};
int n, m, k, res;
int map[51][51];
int copy_map[51][51];
vector<CALC> calc, sel;
int visited[6];

void dfs(int node) {

	if (sel.size() == k) {


		for (int i = 0; i < k; i++) {

			int ly = sel[i].r - sel[i].s;
			int lx = sel[i].c - sel[i].s;	//왼쪽 상단
			int ry = sel[i].r + sel[i].s;
			int rx = sel[i].c + sel[i].s;	//오른쪽 하단

			int temp_map[51][51] = { 0, };

			int sy = ly;
			int sx = lx;

			while (1) {
				if (ly == ry && lx == rx) break;

				while (1) {
					if (sx + 1 <= rx) {
						temp_map[sy][sx + 1] = map[sy][sx];
						sx += 1;
					}
					else break;
				}

				while (1) {
					if (sy + 1 <= ry) {
						temp_map[sy + 1][sx] = map[sy][sx];
						sy += 1;
					}
					else break;
				}

				while (1) {
					if (sx - 1 >= lx) {
						temp_map[sy][sx - 1] = map[sy][sx];
						sx -= 1;
					}
					else break;
				}

				while (1) {
					if (sy - 1 >= ly) {
						temp_map[sy - 1][sx] = map[sy][sx];
						sy -= 1;
					}
					else break;
				}

				sy += 1, sx += 1;
				ly += 1, lx += 1, rx -= 1, ry -= 1;
			}

			for (int y = 1; y <= n; y++) {
				for (int x = 1; x <= m; x++) {
					if (temp_map[y][x] != 0) {
						map[y][x] = temp_map[y][x];
					}
				}
			}
		}


		for (int y = 1; y <= n; y++) {
			int candi = 0;
			for (int x = 1; x <= m; x++) {
				candi += map[y][x];
			}
			if (candi < res) res = candi;
		}

		for (int y = 1; y <= n; y++) {
			for (int x = 1; x <= m; x++) {
				map[y][x] = copy_map[y][x];
			}
		}

		return;
	}

	for (int i = 0; i < calc.size(); i++) {
		if (visited[i]) continue;
		sel.push_back(calc[i]);
		visited[i] = 1;
		dfs(i + 1);
		visited[i] = 0;
		sel.pop_back();
	}
}

int main(void) {

	scanf("%d %d %d", &n, &m, &k);

	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= m; x++) {
			scanf("%d", &map[y][x]);
			copy_map[y][x] = map[y][x];
		}
	}

	for (int i = 0; i < k; i++) {
		CALC temp;
		scanf("%d %d %d", &temp.r, &temp.c, &temp.s);
		calc.push_back(temp);
	}

	res = 0x7fffffff;
	dfs(0);

	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}