[알고리즘] 배열 돌리기 4

포인트

• 정해진 배열을 잘 돌릴 수 있는가?
• 배열을 밀고 땡긴다라고 생각하면 헷갈릴 수 있다. 값을 복사한다고 생각하면 된다. 그리고 시작지점에 그 다음 번째 값을 복사해주자

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<vector>

#define endl "\n"
#define MAX 50 + 1
#define K_MAX 6
using namespace std;

struct info {
	int R, C, S;
};

int n, m, k, answer;
int map[MAX][MAX];
int cmap[MAX][MAX];
bool sel[K_MAX];
vector<info> vc;
vector<int> turn;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int change_Direction(int cur) {
	if (cur == 0) return 3;
	if (cur == 1) return 2;
	if (cur == 2) return 0;
	if (cur == 3) return 1;
}

void simulation(info T) {
	/*=======================================================================*/
	/*실제로 배열을 돌려보는 함수.
	  1. while문을 통해서 각 라인별이 아닌, 한 번에 처리하는 식으로 구현.
	  2. 돌려야 할 사각형의 범위 밖으로 나가는 경우 방향을 바꿔주는 식으로 구현. */
	/*=======================================================================*/

	int sx = T.R - T.S;
	int sy = T.C - T.S;
	int ex = T.R + T.S;
	int ey = T.C + T.S;
	int count = (ex - sx) / 2; // 몇 개의 사각형을 돌려줘야 하는지

	for (int i = 0; i < count; i++) // 돌려야 할 사각형의 갯수만큼 반복
	{
		int x = sx; // x = 시작 X좌표
		int y = sy; // y = 시작 y좌표
		int Temp = cmap[x][y]; // 가장 첫 시작점을 Temp에 임시적으로 저장
		int d = 2; // 0 = 동, 1 = 서, 2 = 남, 3 = 북. 첫 방향은 남쪽 !
		/* 첫 방향을 남쪽으로 잡은 이유
		   - 시계방향으로 배열이 회전되는 것이기 때문에, 이는 어떻게 보면
		     자기 자신을 기준으로 반 시계 방향에 있는 값이 자기 자신의 자리에 위치하게 된다.
		     즉, 시작점을 기준으로 왼쪽 세로변, 하단 가로변, 우측 세로변, 상단 가로변 순서로
		     움직이면서 값을 설정해 주었다. */

		while (1) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			// (nx, ny) = 위에서 말했듯이, 현재 자기자신을 기준으로 한 칸 왼쪽(반시계방향) 에 있는 좌표

			if (nx == sx && ny == sy) // 다시 처음 위치로 돌아오게 된다면
			{
				cmap[x][y] = Temp; // 위에서 저장해둔 임시 저장 값으로 값을 설정 후 종료.
				break;
			}

			if (sx <= nx && nx <= ex - i && sy <= ny && ny <= ey - i) // 현재 사각형의 범위 내에 있는 좌표라면
			{
				cmap[x][y] = cmap[nx][ny]; // 자기자신의 자리에 반 시계방향에 있는 좌표를 넣어준다.
				x = nx; // x값 재설정
				y = ny; // y값 재설정
			}
			else {
				/* 그렇게, 방향을 따라가다 보면 정해진 사각형의 범위를 벗어나는 경우가 존재함.
				   그럴 때는 방향을 바꿔준다.
				   남쪽 -> 동쪽 -> 북쪽 -> 서쪽 순으로 ! */
				d = change_Direction(d);
			}
		}
		sx++;
		sy++;
		/* 그 다음 사각형으로 가기 위한 sx, Sy값 설정.
		   만약, 돌려야 할 사각형의 갯수가 2개이고, 가장 바깥쪽 사각형의 시작점이 (1, 1)이엿다면
		   그 다음으로 돌려야 할 사각형의 시작점은 (2, 2)가 될 것이다.
		   즉, sx++ ,sy++ */
	}
}

int calc() {

	int value = 987654321;
	for (int i = 1; i <= n; i++) {
		int sum = 0;
		for (int j = 1; j <= m; j++) {
			sum += cmap[i][j];
		}
		value = min(value, sum);
	}
	return value;
}

void go(int cnt) {
	if (cnt == k) {
		memcpy(cmap, map, sizeof (map));
		for (int i = 0; i < turn.size(); i++) {
			int order = turn[i];
			simulation(vc[order]);
		}
		answer = min(answer, calc());
		return;
	}

	/* 배열을 돌리는 순서를 정하기 위한 (순열 생성을 위한) 반복문. */
	for (int i = 0; i < vc.size(); i++) {
		if (sel[i] == true) continue;
		sel[i] = true;
		turn.push_back(i);
		go(cnt + 1);
		turn.pop_back();
		sel[i] = false;
	}
}

int main(void) {
	answer = 987654321;
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < k; i++) {
		int r, c, s;
		cin >> r >> c >> s;
		vc.push_back({r, c, s});
	}

	go(0);
	cout << answer << endl;

	return 0;
}

python

import sys
from itertools import permutations
from copy import deepcopy


def rotate(operation, copy_data):
    global answer
    for case in operation:
        row, column, s = case
        row -= 1
        column -= 1
        print(row, column, s)
        for k in range(s, 0, -1):  # 횐전 개수
            top_right = copy_data[row - k][column + k]
            # 오른쪽 위치를 저장한다.
            bottom_left = copy_data[row + k][column - k]
            # 왼쪽 아래 위치를 저장한다.
            bottom_right = copy_data[row + k][column + k]
            # 오른쪽 아래 위치를 저장한다.

            for y in range(column + k, column - k, -1):  # 위 행을 민다
                copy_data[row - k][y] = copy_data[row - k][y - 1]

            for x in range(row + k, row - k, -1):  # 오른쪽 열을 민다
                copy_data[x][column + k] = copy_data[x - 1][column + k]

            for y in range(column - k, column + k):  # 아래쪽 행을 떙긴다
                copy_data[row + k][y] = copy_data[row + k][y + 1]

            for x in range(row - k, row + k):  # 왼쪽 열을 땡긴다
                copy_data[x][column - k] = copy_data[x + 1][column - k]
            # 이렇게 땡기면 처음 시작 지점을 제외하고 
            # 빈 공간을 채워준다.
            copy_data[row - k + 1][column + k] = top_right
            copy_data[row + k][column + k - 1] = bottom_right
            copy_data[row + k - 1][column - k] = bottom_left

    for row in copy_data:
        answer = min(answer, sum(row))


n, m, k = map(int, sys.stdin.readline().split())
data = [list(map(int, input().split())) for _ in range(n)]
rotates = [list(map(int, input().split())) for _ in range(k)]

answer = 987654321

for operation in permutations(rotates, k):
    rotate(operation, deepcopy(data))

print(answer)