[백준][17406번] 배열 돌리기 4

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

풀이과정

1. 주어진 연산을 모두 한 번씩 이용하였을 때 행의 값이 최솟값이 되는 수를 구하는 문제이다.

2. 완전탐색으로 연산의 순서를 바꿔가면서 모든 경우의 수를 구했다.

3. 연산이 모두 사용되었을 때 최솟값을 구했다. 

 

소스코드(c++)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
struct rotation {
	int r;
	int c;
	int s;
}typedef rot;

vector<rot> operation;
int map[50][50];
int used[6];
int N, M, K;
int answer = 987654321;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void checkAnswer()
{
	for (int i = 0; i < N; i++) {
		int minVal = 0;
		for (int j = 0; j < M; j++) {
			minVal += map[i][j];
		}
		answer = min(answer, minVal);
	}
}

void rotationMap(int idx)
{
	rot oper = operation[idx];
	int count = 0;
	for (int i = 0; i < oper.s; i++) {
		int cx = oper.c - oper.s + i;
		int cy = oper.r - oper.s + i;
		if (cx < 0 || cy < 0 || cx >= M || cy >= N) {
			continue;
		}
		int beginX = cx;
		int beginY = cy;
		int endX = oper.c + oper.s - i;
		int endY = oper.r + oper.s - i;
		int prev = map[cy][cx];
		for (int j = 0; j < 4; j++) {
			while (1) {
				int nx = cx + dx[j];
				int ny = cy + dy[j];
				if (nx < beginX || ny < beginY || nx > endX || ny > endY) {
					break;
				}
				int tmp = map[ny][nx];
				map[ny][nx] = prev;
				prev = tmp;
				cx = nx;
				cy = ny;
			}
		}
	} 
}

void solution(int cur, int depth)
{
	if (depth >= K) {
		checkAnswer();
		return;
	}
	int cpyMap[50][50] = { 0, };
	memcpy(cpyMap, map, sizeof(map));
	for (int i = 0; i < K; i++) {
		if (used[i] == 0) {
			used[i] = 1;
			rotationMap(i);
			solution(i + 1, depth + 1);
			used[i] = 0;
			memcpy(map, cpyMap, sizeof(map));
		}
	}
}

int main()
{
	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++) {
		int r, c, s;
		scanf("%d %d %d", &r, &c, &s);
		rot tmp = { r - 1, c - 1, s };
		operation.push_back(tmp);
	}
	solution(0, 0);
	printf("%d\n", answer);
}

결과