[BOJ] 17406 - 배열 돌리기 4

문제 링크

서론)
지금까지는 기록용으로만 사용해서 문제 해결방법에 대한 설명이 너무 성의없었던 것 같다.
분명 미래의 내가 이걸 보면 그래서 어떻게 푼다는 건데? 하고 생각할 것이다.
미래의 나를 위해 문제를 조금 더 상세하게 설명하기로 한다.

이 문제는 알고리즘이 들어갈 것이 없이 그냥 단순히 구현 능력만을 보는 문제다.
문제는 다 구현해놓고 왜 틀렸습니다가 나오는지 이해할수 없어 많은 시간을 고통받았는데..
결론을 말하자면 next_permutation을 제대로 이해하지 못해서 발생한 문제였다.
이에 대한 반성으로 주의점에 대한 글을 정리해놨으니 미래의 내가 꼭 읽어보길 바란다.

구현한 방법은 간단한데,

1. 명령어의 순서를 순열함수를 이용해 구한다.
2. 순서가 정해진 명령어를 수행한다
   1. 각 명령어마다 rotate함수를 통해 배열을 잘 돌려준다.
   2. 모든 명령어를 수행하고 cal_min함수를 통해 해당 배열 A의 최솟값을 구해 현재까지의 최솟값과 비교하여 갱신한다.

나름 상세하게 적는다고 적었는데 별로 친절하지 않은 것 같다..
그치만.. 그냥 구현인데 이 이상 어떻게 설명해야 할 지 모르겠다.. 미래의 내가 꼭 이 설명을 보고도 이해할 수 있기를..

소스코드

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <string.h>
using namespace std;
typedef tuple<int, int, int> T;

int n, m, A[55][55], buf[55][55], ans = INT32_MAX;
int dr[4][2] = { {0, -1}, {1, 0}, {0, 1},{-1, 0} };
int dc[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
vector<T> v;

int cal_min(void) {
	int rtn = INT32_MAX;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = 0; j < m; j++)
			sum += buf[i][j];
		rtn = min(rtn, sum);
	}
	return rtn;
}

void rotate(int r, int c, int s) {
	int rotated[55][55] = { 0, };
	rotated[s][s] = buf[r][c];
	for (int i = 1; i <= s; i++)
		for (int k = 0; k < 4; k++)
			for (int j = -i; j < i; j++) {
				int x = j * dr[k][0] + i * dr[k][1], y = j * dc[k][0] + i * dc[k][1];
				rotated[x + s + dr[k][0]][y + s + dc[k][0]] = buf[x + r][y + c];
			}

	for (int i = 0; i < 2 * s + 1; i++)
		for (int j = 0; j < 2 * s + 1; j++)
			buf[r + i - s][c + j - s] = rotated[i][j];
}

void go(void) {
	memcpy(buf, A, sizeof(A));
	for (T q : v) {
		int r = get<0>(q), c = get<1>(q), s = get<2>(q);
		rotate(r, c, s);
	}
	ans = min(cal_min(), ans);
}

int main(void) {
	int k, r, c, s;
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", A[i] + j);
		}
	}
	for (int i = 0; i < k; i++) {
		scanf("%d %d %d", &r, &c, &s);
		v.push_back({ r - 1, c - 1, s });
	}

	sort(v.begin(), v.end());

	do {
		go();
	} while (next_permutation(v.begin(), v.end()));
	printf("%d", ans);
	return 0;
}