[백준] 17406 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

순열을 구해주는 것은 어렵지 않았지만

회전을 해주는 과정에서 헤매었다.

 

시계방향으로 한 칸씩 이동시키는 회전 함수

void turn_box(TURN cmd){
	int sy = cmd.r - cmd.s;
	int sx = cmd.c - cmd.s;
	int ey = cmd.r + cmd.s;
	int ex = cmd.c + cmd.s;
	
    // 사각형을 밖에서부터 점점 좁혀가면서 수행하는데, 
    // ey > sy ... 의 조건이 걸릴 경우, 중심까지 좁힌 것이기 때문에 반복문을 나온다.
	while(ey > sy && ex > sx) { 
		int cy = sy;
		int cx = sx;
		int target = copy_map[cy][cx]; // 옮길 값을 target에 저장한다.
		int dir = 0;

		while(true) {

			int ny = cy + dy[dir];
			int nx = cx + dx[dir];

			// 처음위치로 돌아오게 된다면
			if(ny == sy && nx == sx){
				copy_map[ny][nx] = target;
				break;
			}
			// 끝까지 탐색했다면 방향을 바꿔준다.
			if(nx < sx || ny < sy || nx > ex || ny > ey) {
				dir = (dir+1) % 4;
			 	ny = cy + dy[dir];
			 	nx = cx + dx[dir];
			}
			// 옮길 자리에 있는 값을 tmp 에 저장한 후
			int tmp = copy_map[ny][nx];
            // 숫자를 옮겨준다
			copy_map[ny][nx] = target;
            // 기존에 있던 값이 다음 수행에서는 target 이 된다.
			target = tmp;
			
            // 위치 재설정
			cy = ny; cx = nx;
		}
        // 사각형을 좁혀준다.
		sy++; sx++;
		ex--; ey--;

	}

	
}

전체 코드

#include <iostream>
#include <vector>
using namespace std;

struct TURN {
	int r, c, s;
};

vector <TURN> turn;

int n, m, k;
int map[60][60];
bool visit[10];
int choice[10];
int copy_map[60][60];
int answer = 987654321;

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

void turn_box(TURN cmd){
	int sy = cmd.r - cmd.s;
	int sx = cmd.c - cmd.s;
	int ey = cmd.r + cmd.s;
	int ex = cmd.c + cmd.s;

	while(ey > sy && ex > sx) {
		int cy = sy;
		int cx = sx;
		int target = copy_map[cy][cx];
		int dir = 0;

		while(true) {

			int ny = cy + dy[dir];
			int nx = cx + dx[dir];

			// 처음위치로 돌아오게 된다면
			if(ny == sy && nx == sx){
				copy_map[ny][nx] = target;
				break;
			}
			
			if(nx < sx || ny < sy || nx > ex || ny > ey) {
				dir = (dir+1) % 4;
			 	ny = cy + dy[dir];
			 	nx = cx + dx[dir];
			}

			int tmp = copy_map[ny][nx];
			copy_map[ny][nx] = target;
			target = tmp;
			
			cy = ny; cx = nx;
		}
		sy++;
		sx++;
		ex--;
		ey--;

	}

	
}


void dfs(int cnt, int target) {

	if(cnt == target) {

		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++)
				copy_map[i][j] = map[i][j];

		for(int i=0; i<target; i++){
			TURN cur = turn[choice[i]];
			turn_box(cur);
		}

		for(int i=1; i<=n; i++) {
			int row = 0;
			for(int j=1; j<=m; j++)
				row += copy_map[i][j];
			if(row < answer)
				answer = row;
		}
		return;
	}

	for(int i=0; i<target; i++) {
		if (visit[i]) continue;
		visit[i] = true;
		choice[cnt] = i;
		dfs(cnt+1, target);
		visit[i] = false;
	}

}


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

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

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

	dfs(0, k);
	printf("%d\n", answer);
}