[C/C++] 백준 - 17406번 : 배열 돌리기4

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

17406번: 배열 돌리기 4

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3 2 1 1 4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1] A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6] ↑ ↓ A[2][1] A[2][2] A[2][3] → A[2][4] → A[2][5] A[2][6] ↑ ↑ ↓ ↓ A[3][1] A[3][2] A[3][3] A[3][4] A[3][5] A[3][6] ↑ ↑ ↓ ↓ A[4][1] A[4][2] A[4][3] ← A[4][4] ← A[4][5] A[4][6] ↑ ↓ A[5][1] A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6] A[6][1] A[6][2] A[6][3] A[6][4]   A[6][5] A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

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

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

 

이 문제는 시물레이션 문제이면서 조합을 이용해야 하는 문제이다.

조합을 통해 각 경우의 수를 모두 진행해서 최소값을 구해주면 되는 문제이지만, 나름 까다로운 문제이다.

 

일단 나는 배열을 입력받고, 입력받는 배열까지 총 3개의 배열을 선언했다.

그 이유는 경우에 수만큼 처음부터 진행해주어야 하기 때문에 초기 배열 상태를 저장해주는 배열 1개, 

각 상태가 진행됨에 따라 초기화 해주는 배열 1개, 초기화 해주고 그 배열의 직전 상태를 저장해주는 배열 1개

초기화 해주는 배열은 직전 상태를 저장해주는 배열의 값을 가져와 초기화 시켜주는 방식이다.

 

조합은 next_permutation함수를 사용했다.

이 문제에서 가장 까다로운 부분은 아마 시계방향으로 배열을 회전시키는 것인 것 같다.

지금까지 사용해왔던 회전과는 조금 다른 방식이라 생각이 필요했다.

 

나는 바깥에서 안쪽으로 하나씩 줄여가며 회전시키는 방법을 사용했다. 그리고 더 이상 회전시킬 수 없는 범위라면 바로 해당 회전은 끝냈다. 그러면 회전은 어떻게 시켰냐?

예제에서도 나와있고, 그림을 그려보면 회전은 결국 사각형이 주어지고 그 사각형에서 가장 바깥 라인만 따라 회전을 하게 된다. 그리고 모든 라인을 회전시켜 처음으로 되돌아오면 가장 바깥 라인 회전이 끝난 것이고, 라인을 안쪽으로 하나씩 줄여가다보면 결국 회전을 할 수 없는 곳까지 들어갈 수 있다. 이걸 좌표를 이용한 방법을 사용했다.

 

사각형이기에 4개의 꼭짓점이 주어진다. 그리고 각 꼭짓점의 좌표는 가로의 변은 y의 좌표가 같고, 세로의 좌표는 x의 좌표가 같다. 여기까지 이해했으면 이제 어떻게 해야할지 감이 올 것이다.

 

사각형의 윗변 -> 오른쪽으로 하나씩 이동

사각형의 오른쪽 변 -> 아래쪽으로 하나씩 이동

사각형의 아래변 -> 왼쪽으로 하나씩 이동

사각형의 왼쪽변 -> 위쪽으로 하나씩 이동

 

위 처럼 진행하면, 시계방향으로 좌표를 하나씩 옮기는 방법이 되는 것이다.

이걸 코드로 작성하면 각 방향대로 이동은 for문 하나씩 총 4개로 회전시킬 수 있다.

 

나머지는 코드를 통해 이해해보자

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

// BOJ :: https://www.acmicpc.net/problem/17406
struct node {
	int y;
	int x;
};

int N, M, K, start_y, start_x, end_y, end_x;
int adj[51][51], copy_adj[51][51], Init_adj[51][51];
int r[6], c[6], s[6];
int Rotate[6];

// 초기 상태 배열로 초기화
void Init_Copy() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			adj[i][j] = Init_adj[i][j];
		}
	}
}

// 회전 끝나고 직전 배열로 초기화
void Copy() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copy_adj[i][j] = adj[i][j];
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> adj[i][j];
			Init_adj[i][j] = adj[i][j];
		}
	}

	for (int i = 0; i < K; i++) {
		cin >> r[i] >> c[i] >> s[i];
		Rotate[i] = i;
	}
	
	int Answer = INF;
	do {
		Init_Copy();
		for (int i = 0; i < K; i++) {
			Copy();
			start_y = r[Rotate[i]] - s[Rotate[i]];
			start_x = c[Rotate[i]] - s[Rotate[i]];

			end_y = r[Rotate[i]] + s[Rotate[i]];
			end_x = c[Rotate[i]] + s[Rotate[i]];

			int ps = 0;
			while (1){
				// 1은 왼쪽 위 꼭짓점, 2는 오른쪽 위 꼭짓점, 3은 왼쪽 아래 꼭짓점, 4는 오른쪽 아래 꼭짓점
				// ps는 바깥 라인부터 하기 위해 존재, while문 한 번 돌고오면 안쪽라인으로 들어가야하기 때문에 ps++
				node start1, start2, start3, start4;
				start1.y = start_y + ps, start1.x = start_x + ps;
				start2.y = start_y + ps, start2.x = end_x - ps;
				start3.y = end_y - ps, start3.x = start_x + ps;
				start4.y = end_y - ps, start4.x = end_x - ps;

				// 가로
				int len1 = start2.x - start1.x;
				// 세로
				int len2 = start3.y - start1.y;

				// 범위가 0보다 작거나 같아지면 더 이상 회전시키지 않는다
				if (len1 <= 0 || len2 <= 0) break;

				// 첫번째 오른쪽으로
				for (int x = start1.x + 1; x <= start2.x; x++) {
					adj[start1.y][x] = copy_adj[start1.y][x - 1];
				}
				// 두번째 아래로
				for (int y = start2.y + 1; y <= start3.y; y++) {
					adj[y][start2.x] = copy_adj[y - 1][start2.x];
				}
				// 세번째 왼쪽으로
				for (int x = start4.x - 1; x >= start3.x; x--) {
					adj[start4.y][x] = copy_adj[start4.y][x + 1];
				}
				// 네번째 위로
				for (int y = start3.y - 1; y >= start1.y; y--) {
					adj[y][start1.x] = copy_adj[y + 1][start1.x];
				}
				ps++;
			}
		}

		// 배열 adj값 초기화
		int cur_Answer = INF;
		for (int i = 1; i <= N; i++) {
			int ps = 0;
			for (int j = 1; j <= M; j++) {
				ps += adj[i][j];
			}
			cur_Answer = min(cur_Answer, ps);
		}
		// 답으로 출력할 전체 최소값 초기화
		Answer = min(Answer, cur_Answer);

	} while (next_permutation(Rotate, Rotate+K));

	cout << Answer << endl;

	return 0;
}