acmicpc17406.md

배열 돌리기 4

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

개요

배열을 돌리는 명령어가 좌표와 거리의 형태로 주어지면 좌표를 기준으로 거리보다 가까운 거리에 있는 점들의 배열을 한 칸씩 시계방향으로 돌린다. 명령어들의 순서에 따라 변하는 배열의 각 행에 있는 모든 수의 합 중 최솟값을 구하는 문제

분석

순서를 다 정하고(수열을 다 구하고) 배열을 돌리는 방법과 순서를 정하며(수열을 만들며) 배열을 돌리는 방법 두 가지가 있다. 수열을 다 구하고 배열을 돌리는 방법은 배열을 계속 초기화해주어야 한다. 수열을 만들며 배열을 돌리는 방법을 선택하면 한 번 돌린 뒤 순서를 다 정하고 복귀(리턴) 시 반대방향으로 돌려주어야 한다. 이는 원래 배열을 갱신하는 진행방향의 반대방향으로 진행하며 배열을 갱신해주면 된다.

예를 들어 왼쪽 위 좌표부터 시작하여 시계방향으로 갱신한다면 반대방향인 아래, 오른쪽, 위, 왼쪽 의 순서로 진행하며 갱신하게 된다. 원래대로 돌려놓고 싶다면 시계방향의 반대인 반시계방향으로 갱신해야한다. 따라서 시계방향인 오른쪽, 아래, 왼쪽, 위 의 순서로 갱신하면 된다.

알고리즘

1. 명령어(r, c, s)들을 배열에 저장한다.
2. dfs로 수열을 모두 탐색한다.
3. 수열이므로 chk를 하며 dfs를 탐색한다.
4. dfs로 수열을 탐색할 때마다 해당 수(인덱스)의 돌리기 명령어로 배열을 돌린다.
5. dfs 복귀시 돌렸던 배열을 원래 배열로 다시 돌려주고 chk를 해제한다.
6. 수열이 다 끝나면 최솟값을 갱신한다.

소스

#include <stdio.h>

int map[60][60], h[10][3], chk[10], n, m, k, min = 999999, dd[8][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,0}, {0,1},{-1,0}, {0,-1} };

void hwe(int a, int b, int r, int d)
{
	int i, j, rr, bang, x, y, cho;
	
	for (rr = 1; rr <= r; rr++)
	{
		x = a - rr;
		y = b - rr;
		cho = map[x][y];
		for (i = 0; i < 4; i++)
		{
			if (d == -1) bang = i;
			else bang = 4 + i;
			for (j = 1; j <= rr*2; j++)
			{
				map[x][y] = map[x + dd[bang][0]][y + dd[bang][1]];
				if (i == 3 && j == rr*2) map[x][y] = cho;
				x = x + dd[bang][0];
				y = y + dd[bang][1];
			}
		}
	}
}
void cal()
{
	int i, j, sum;
	for (i = 1; i <= n; i++)
	{
		sum = 0;
		for (j = 1; j <= m; j++) sum += map[i][j];
		if (sum < min) min = sum;
	}
}
void dfs(int st)
{
	int i, j;
	if (st == k)
	{
		cal();
		return;
	}
	for (i = 1; i <= k; i++)
	{
		if (chk[i] == 0)
		{
			chk[i] = 1;
			hwe(h[i][0], h[i][1], h[i][2], 1);
			dfs(st + 1);
			hwe(h[i][0], h[i][1], h[i][2], -1);
			chk[i] = 0;
		}
	}
}
int main()
{
	int i, j;
	scanf("%d%d%d", &n, &m, &k);
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= m; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	for (i = 1; i <=k; i++)
	{
		for(j=0; j<3; j++)
		{
			scanf("%d", &h[i][j]);
		}
	}
	dfs(0);
	printf("%d", min);
}