백준 17406 : 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

주어지는 입력에 따라 배열의 부분 행렬에 대하여 시계 방향으로 한 칸씩 이동시키는 문제이다. 이전에 포스팅한 배열 돌리기 1과 유사한 매커니즘인데, 방향이 반대이고 부분 행렬을 회전시킨다는 차이점이 있다.

(이전 문제 풀이 참고 링크 -https://unfunhy.tistory.com/50)

백준 16926 : 배열 돌리기 1

 

케이스를 나누는 핵심 방법은 이전 문제와 동일한 방법을 사용했고, 이번 문제는 주어지는 커맨드들의 순서를 잘 조합해서 행의 합이 가장 작은 경우를 찾는 문제라 백트래킹 방법으로 문제를 해결했다.

 

#include <iostream>

#define min(a,b) a<b?a:b
using namespace std;

struct CMD {
	int x, y, offset;
};

int n, m, k;
int min_val = 5e3;
int board[50][50];
bool used_cmd[6];
CMD cmd[6];

void move(int& curx, int& cury, bool undo, int sx, int sy, int ex, int ey) {
	if (!undo) {
		if (cury == sy && curx != sx) --curx;
		else if (curx == ex && cury != sy) --cury;
		else if (cury == ey && curx != ex) ++curx;
		else if (curx == sx && cury != ey) ++cury;
	}
	else {
		if (cury == sy && curx != ex) ++curx;
		else if (curx == ex && cury != ey) ++cury;
		else if (cury == ey && curx != sx) --curx;
		else if (curx == sx && cury != sy) --cury;
	}
}

void rotate(int sx, int sy, int ex, int ey, bool undo=false) {
	//기저 조건
	if (ex - sx < 2) return;

	int curx, cury, nx, ny, tmp;
	
	if (!undo) curx = sx, cury = sy + 1;
	else curx = sx + 1, cury = sy;

	tmp = board[cury][curx];
	while (!(curx == sx && cury == sy)) {
		nx = curx, ny = cury;
		move(curx, cury, undo, sx, sy, ex, ey);
		board[ny][nx] = board[cury][curx];
	}
	board[sy][sx] = tmp;

	++sx, ++sy, --ex, --ey;
	rotate(sx, sy, ex, ey, undo);
}

void dfs(int lvl) {
	//기저 조건
	if (lvl >= k) {
		for (int y = 0; y < n; y++) {
			int sum = 0;
			for (int x = 0; x < m; x++) {
				sum += board[y][x];
			}
			min_val = min(min_val, sum);
		}
		return;
	}

	int curx, cury, offset;
	int sx, sy, ex, ey;

	for (int i = 0; i < k; i++) {
		if (used_cmd[i]) continue;

		cury = cmd[i].y - 1;
		curx = cmd[i].x - 1;
		offset = cmd[i].offset;
		
        //회전 영역 바운더리 설정
		sx = curx - offset; if (sx < 0) sx = 0;
		sy = cury - offset; if (sy < 0) sy = 0;
		ex = curx + offset; if (ex >= m) ex = m - 1;
		ey = cury + offset; if (ey >= n) ey = n - 1;
		
        //백트래킹
		rotate(sx, sy, ex, ey);
		used_cmd[i] = 1;

		dfs(lvl + 1);
		
        //undo, 반대 방향으로 회전
		rotate(sx, sy, ex, ey, 1);
		used_cmd[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
    //input
	cin >> n >> m >> k;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> board[y][x];
		}
	}
	for (int i = 0; i < k; i++) {
		cin >> cmd[i].y >> cmd[i].x >> cmd[i].offset;
	}

	//solution
	dfs(0);
	cout << min_val;

	return 0;
}

메모리: 2040 kb

시간: 16 ms