boj, 백준) 17406. 배열 돌리기 4 ( C / C++)

1. 문제 링크

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

17406번: 배열 돌리기 4

2. 문제 개요

 회전 연산이 주어졌을 때, 회전 순서를 적절히 정해서 배열 A의 값의 최솟값을 구하는 문제.

 

3. 문제 힌트

  회전순서 -> DFS

  회전 구현 실수 안 할 것. -> 구현 시 맵 복사해두기.. 등등

 

4. 문제 풀이

 회전연산의 순서를 잘 정한다면 어려운 점이 없는 문제다.

 

5. 코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int map[50][50];
int n, m, s, k;
int order[6];
bool pick[6] = { false, };
int ret = 0x7fffffff;

struct COORD {
	int y, x, s;
}r[6];
void copymap(int dest[][50], int src[][50])
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dest[i][j] = src[i][j];
	return;
}
void rotate(int clone[][50],COORD cur)
{
	cur.x--;
	cur.y--;
	for (int s = 1; s <= cur.s; s++)
	{
		//오른쪽 위부터 시계방향으로
		int temp = clone[cur.y - s][cur.x + s];

		for (int j = cur.x + s; j > cur.x - s; j--)
			clone[cur.y - s][j] = clone[cur.y - s][j - 1];

		for (int i = cur.y - s; i < cur.y + s; i++)
			clone[i][cur.x - s] = clone[i + 1][cur.x - s];

		for (int j = cur.x - s; j < cur.x + s; j++)
			clone[cur.y + s][j] = clone[cur.y + s][j + 1];

		for (int i = cur.y + s; i > cur.y - s; i--)
			clone[i][cur.x + s] = clone[i - 1][cur.x + s];

		clone[cur.y - s + 1][cur.x + s] = temp;
	}
}
void dfs(int depth)
{
	if (depth == k)
	{
		int clone[50][50];
		copymap(clone, map);
		for (int i = 0; i < k; i++)
			rotate(clone,r[order[i]]);
		
		int sum = 0x7fffffff;

		for (int i = 0; i < n; i++)
		{
			int temp = 0;
			for (int j = 0; j < m; j++)
			{
				temp += clone[i][j];
			}
			sum = min(sum, temp);
		}

		ret = min(ret, sum);
		return;
	}
	for (int i = 0; i < k; i++)
	{
		if (!pick[i])
		{
			pick[i] = true;
			order[depth] = i;
			dfs(depth + 1);
			order[depth] = -1;//unnecessary
			pick[i] = false;
		}
	}
}

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

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

	for (int i = 0; i < k; i++)
		scanf("%d %d %d", &r[i].y, &r[i].x, &r[i].s);

	//permutation
	dfs(0);

	printf("%d", ret);
	return 0;
}

 

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~