[C++] 백준 17406 배열돌리기4

문제 링크

---

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

접근 방법

---

 처음에 문제를 해결하고 나서 왜맞틀을 시전했던 문제입니다. 문제를 잘 못 이해해서 생긴 문제인데 문제에서 배열의 회전 명령어를 순차적으로 실행하는 것이 아닌 주어진 명령어의 모든 조합을 다 실행하여 그 중 최소를 구하는 문제였습니다. 

 

문제 풀이의 순서는 다음과 같습니다.

1. 가능한 명령의 조합을 구한다.

2. 한 조합에서 한 명령어를 실행한다.

3. 한 명령어를 실행한다.

4. 한 명령어에 s~1까지 순차적으로 배열을 회전 시킨다.

5. 한 조합의 명령어를 모두 실행시킨 후 배열의 값을 구한다.

6. 다음 조합도 위의 과정을 실행하며 최솟값을 갱신한다.

 

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct info {
	int r; int c; int s;
};

vector <vector<int>> map;
vector <info> inst;
int N, M, K;

void init() {
	
	cin >> N >> M >> K;

	for (int i = 0; i < N; i++) {
		vector<int> v;
		for (int j = 0; j < M; j++) {
			int num; cin >> num;
			v.push_back(num);
		}
		map.push_back(v);
	}
	for (int i = 0; i < K; i++) {
		int r, c, s;
		cin >> r >> c >> s;
		inst.push_back({ r - 1, c - 1, s });
	}
}

vector<vector<int>> sequence(vector<int> &seq, vector<vector<int>> &seqs, vector<bool> &visited) {

	if (seq.size() == inst.size()) {
		seqs.push_back(seq);
		return seqs;
	}
	for (int i = 0; i < inst.size(); i++) {
		if (!visited[i]) {
			visited[i] = true;
			seq.push_back(i);
			sequence(seq, seqs, visited);
			visited[i] = false;
			seq.pop_back();
		}
	}
	return seqs;
}

int findMin(vector<vector<int>> newmap) {
	
	int minimum = 0xFFFFFFF;

	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = 0; j < M; j++)
			sum += newmap[i][j];
		minimum = min(sum, minimum);
	}
	return minimum;
}

void rotate(int x, int y, int dist, vector<vector<int>> &ret) {

	vector<vector<int>> tmp = ret;

	for (int i = y - dist; i < y + dist; i++) 
		ret[x - dist][i + 1] = tmp[x - dist][i]; //높이 고정
	for (int i = x - dist; i < x + dist; i++)
		ret[i + 1][y + dist] = tmp[i][y + dist];  // 축 고정
	for (int i = y + dist; i > y - dist; i--)
		ret[x + dist][i - 1] = tmp[x + dist][i]; //높이 고정
	for (int i = x + dist; i > x - dist; i--)
		ret[i - 1][y - dist] = tmp[i][y - dist];  // 축 고정
}

int processing(vector<int> seq) { // 한 명령어 집합에 대한 것
	
	vector<vector<int>> newmap = map;

	for (int i = 0; i < seq.size(); i++) {

		int r = inst[seq[i]].r;
		int c = inst[seq[i]].c;
		int s = inst[seq[i]].s;

		for (int j = 1; j <= s; j++)
			rotate(r, c, j, newmap);
	}
	return findMin(newmap);
}

int solve() {
	
	vector <vector<int>> seqs;
	vector <int> seq;
	vector <bool> visited(6, false);
	int minimum = 0xFFFFFFF;

	seqs = sequence(seq, seqs, visited);

	for (int i = 0; i < seqs.size();i++) 
		minimum = min(minimum, processing(seqs[i]));
	
	return minimum;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	init();

	cout << solve() << "\n";
}

개발 환경 : VS2017

질문, 지적 환영합니다!