BOJ 17406 : 배열 돌리기 4 (A형 상시)

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/17406

 

이후 설명 및 입/출력은 링크 참고

 

MAP은 (1, 1)부터 input을 받고, COMMAND 구조체에 (r, s, c)를 저장한다.

#define MAX (50 + 10)

int N, M, K;
int MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int s;
}COMMAND;

COMMAND command[10];

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);

	for (int i = 1; i <= K; i++)
		scanf("%d %d %d", &command[i].r, &command[i].c, &command[i].s);
}

---

명령에 대한 순서를 임의로 정해서 배열 A의 최솟값을 구해야하므로, 순열을 이용하여 경우의 수를 만든다.

순열은 N과 M (1) - 순열 코드를 참고한다.

int list[10];
int visit[10];

int MINANS = 0x7fff0000;
void DFS(int L)
{
	if (L == K)
	{
		/* simulation */

		return;
	}

	for (int com = 1; com <= K; com++) /* 실행할 command 저장 */
	{
		if (visit[com] == 1) continue;

		list[L] = com;

		visit[com] = 1;
		DFS(L + 1);
		visit[com] = 0;
	}
}

---

simulation은 아래와 같이 구성된다. 

 

먼저 MAP을 tmpMAP에 복사한다.

list배열에 명령을 실행할 순서가 저장되므로, 실제 rotate 함수를 구현하여 명령을 실행한 후,

배열 A의 값 = 각 행에 있는 모든 수의 합 중 최솟값을 구하고 MINANS를 갱신하면 된다.

if (L == K)
{
	//outputList();
	int tmpMAP[MAX][MAX] = { 0 };
	for (int rr = 1; rr <= N; rr++)
		for (int cc = 1; cc <= M; cc++)
			tmpMAP[rr][cc] = MAP[rr][cc];

	for (int i = 0; i < K; i++)
	{
		int num = list[i]; /* list에 저장된 command 번호 실행 */
		rotate(command[num].r, command[num].c, command[num].s, tmpMAP);
	}

	int min = 0x7fff0000;

	for (int r = 1; r <= N; r++)
	{
		int sum = 0;
		for (int c = 1; c <= M; c++)
			sum += tmpMAP[r][c];

		if (sum < min) min = sum;
	}

	if (min < MINANS) MINANS = min;

	return;
}

---

rotate는 tmpMAP에 map을 복사한 후에, s를 기준으로 모서리를 한 칸씩 시계방향으로 밀어주면 된다.

(r, c)를 기준으로 s만큼 떨어진 모든 배열을 돌리기 때문에 for문으로 반복한다.

void rotate(int r, int c, int s, int map[MAX][MAX])
{
	int tmpMAP[MAX][MAX] = { 0 };
	for (int rr = 1; rr <= N; rr++)
		for (int cc = 1; cc <= M; cc++)
			tmpMAP[rr][cc] = map[rr][cc];

	for (int ss = 1; ss <= s; ss++)
	{
		int sr, sc, er, ec;

		sr = r - ss;
		sc = c - ss;
		er = r + ss;
		ec = c + ss;

		for (int i = sc; i < ec; i++) map[sr][i + 1] = tmpMAP[sr][i];
		for (int i = sr; i < er; i++) map[i + 1][ec] = tmpMAP[i][ec];
		for (int i = ec; i > sc; i--) map[er][i - 1] = tmpMAP[er][i];
		for (int i = er; i > sr; i--) map[i - 1][sc] = tmpMAP[i][sc];
	}
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (50 + 10)

int N, M, K;
int MAP[MAX][MAX];

int list[10];
int visit[10];

typedef struct st
{
	int r;
	int c;
	int s;
}COMMAND;

COMMAND command[10];

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%d", &MAP[r][c]);

	for (int i = 1; i <= K; i++)
		scanf("%d %d %d", &command[i].r, &command[i].c, &command[i].s);
}

void output(int map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void outputList()
{
	for (int i = 0; i < K; i++) printf("%d ", list[i]);
	putchar('\n');
}

void rotate(int r, int c, int s, int map[MAX][MAX])
{
	int tmpMAP[MAX][MAX] = { 0 };
	for (int rr = 1; rr <= N; rr++)
		for (int cc = 1; cc <= M; cc++)
			tmpMAP[rr][cc] = map[rr][cc];

	for (int ss = 1; ss <= s; ss++)
	{
		int sr, sc, er, ec;

		sr = r - ss;
		sc = c - ss;
		er = r + ss;
		ec = c + ss;

		for (int i = sc; i < ec; i++) map[sr][i + 1] = tmpMAP[sr][i];
		for (int i = sr; i < er; i++) map[i + 1][ec] = tmpMAP[i][ec];
		for (int i = ec; i > sc; i--) map[er][i - 1] = tmpMAP[er][i];
		for (int i = er; i > sr; i--) map[i - 1][sc] = tmpMAP[i][sc];
	}
}

int MINANS = 0x7fff0000;
void DFS(int L)
{
	if (L == K)
	{
		//outputList();
		int tmpMAP[MAX][MAX] = { 0 };
		for (int rr = 1; rr <= N; rr++)
			for (int cc = 1; cc <= M; cc++)
				tmpMAP[rr][cc] = MAP[rr][cc];

		for (int i = 0; i < K; i++)
		{
			int num = list[i]; /* list에 저장된 command 번호 실행 */
			rotate(command[num].r, command[num].c, command[num].s, tmpMAP);
		}

		int min = 0x7fff0000;

		for (int r = 1; r <= N; r++)
		{
			int sum = 0;
			for (int c = 1; c <= M; c++)
				sum += tmpMAP[r][c];

			if (sum < min) min = sum;
		}

		if (min < MINANS) MINANS = min;

		return;
	}

	for (int com = 1; com <= K; com++) /* 실행할 command 저장 */
	{
		if (visit[com] == 1) continue;

		list[L] = com;

		visit[com] = 1;
		DFS(L + 1);
		visit[com] = 0;
	}
}

int main(void)
{
	input();

	DFS(0);

	printf("%d\n", MINANS);

	return 0;
}