백준 17406 c++ "배열 돌리기 4" -PlusUltraCode-

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

 

[필자 사고]

구현 문제이다.

구현에서도 백트래킹 알고리즘과 재귀를 이용하여 해당 문제를 해결했다.

하나의 알고리즘에 여러 복합적 알고리즘들이 있어서 구현문제는 참 좋다고 느껴졌다.

[코드 해설]

1. struct Node

• rotateArr2에 들어가는 회전 연산 정보를 담는 구조체입니다.
• 회전의 중심 좌표 (sero, garo)와 회전 범위 S를 저장합니다.
• 좌표는 입력 받을 때 0-indexed로 변환됩니다 (-1 처리).

---

2. void Input()

• 배열 크기 N×M과 회전 연산 개수 K를 입력받습니다.
• arr 배열을 초기화하고 입력받은 값으로 채웁니다.
• 이후 회전 연산 K개를 입력받아 rotateArr2 벡터에 저장합니다.
• 회전 연산의 중심 좌표와 범위가 주어지며, 입력 좌표는 1-indexed이므로 0-indexed로 바꿔 저장합니다.

---

3. bool isRotateOk(int leftSero, int leftGaro, int rightSero, int rightGaro)

• 현재 회전해야 할 레이어가 유효한지 확인합니다.
• leftSero >= rightSero 또는 leftGaro >= rightGaro이면 회전할 범위가 없다는 뜻이므로 false를 반환합니다.

---

4. void rotateArr(int leftSero, int leftGaro, int rightSero, int rightGaro)

• 하나의 회전 연산을 수행합니다.
• 회전 범위는 (leftSero, leftGaro)부터 (rightSero, rightGaro)까지입니다.
• 배열을 copyArr에 복사한 뒤, 다음과 같은 순서로 시계 방향으로 한 칸씩 이동시킵니다:
  • 위쪽 행을 오른쪽으로 한 칸씩 밀기
  • 오른쪽 열을 아래로 한 칸씩 밀기
  • 아래쪽 행을 왼쪽으로 한 칸씩 밀기
  • 왼쪽 열을 위로 한 칸씩 밀기
• 그런 다음 arr를 갱신하고, 내부 사각형에 대해 재귀적으로 다시 회전합니다.

※ 이 함수는 값 덮어쓰기 순서에서 겹침 문제가 발생하지 않도록 copyArr를 사용합니다.

---

5. int getMinRowSum()

• 현재 배열 arr에서 각 행의 합을 계산하여, 그 중 가장 작은 값을 반환합니다.
• 문제의 목표는 모든 회전 순서 중에서 배열의 "최소 행 합"을 찾는 것이므로 이 함수는 중요한 기준 함수입니다.

---

6. void Back_Tracking(int size)

• K개의 회전 연산 순서를 전부 탐색하기 위한 백트래킹 함수입니다.
• visited[i]가 false인 연산만 선택하여 적용합니다.
• 회전 순서를 하나 선택하면:
  • 현재 배열을 백업해두고
  • 회전 연산을 수행한 뒤
  • 재귀적으로 다음 단계로 들어갑니다
  • 재귀가 끝나면 배열을 원래 상태로 복구합니다
• 모든 회전 순서를 시도했을 때(size == K)에는 getMinRowSum()을 호출하여 최소 값을 갱신합니다.

---

7. void Game_Start()

• visited 배열을 초기화하고
• Back_Tracking(0)을 호출하여 회전 순서 탐색을 시작합니다.
• 최종적으로 가장 작은 행의 합(resultMinSize)을 출력합니다.

---

8. int main()

• Input() 함수를 통해 입력을 받고
• Game_Start() 함수를 호출하여 로직을 실행합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
	int sero;
	int garo;
	int S;
};

int N, M, K;
vector<vector<int>> arr;
vector<Node> rotateArr2;
int resultMinSize = 99999999;

void Input() {
	cin >> N >> M >> K;
	arr.assign(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> arr[i][k];
		}
	}
	for (int i = 0; i < K; i++) {
		int sero, garo, s;
		cin >> sero >> garo >> s;
		rotateArr2.push_back({ sero-1,garo-1,s });
	}
}

bool isRotateOk(int leftSero, int leftGaro, int rightSero, int rightGaro) {
	if (leftSero >= rightSero || leftGaro >= rightGaro)return false;
	return true;
}

void rotateArr(int leftSero, int leftGaro, int rightSero, int rightGaro) {

	if (isRotateOk(leftSero, leftGaro, rightSero, rightGaro) == false)return;
	
	vector<vector<int>> copyArr = arr;

	for (int i = leftGaro; i < rightGaro; i++) {
	
		copyArr[leftSero][i+1] = arr[leftSero][i];
	}

	for (int i = rightGaro; i > leftGaro; i--) {
		copyArr[rightSero][i-1] = arr[rightSero][i];
	}

	for (int i = leftSero; i < rightSero; i++) {
		copyArr[i + 1][rightGaro] = arr[i][rightGaro];
	}

	for (int i = rightSero; i > leftSero; i--) {
		copyArr[i - 1][leftGaro] = arr[i][leftGaro];
	}

	arr = copyArr;

	rotateArr(leftSero + 1, leftGaro + 1, rightSero - 1, rightGaro - 1);
}

int getMinRowSum() {
	int minSum = 1e9;
	for (int i = 0; i < arr.size(); i++) {
		int sum = 0;
		for (int j = 0; j < arr[0].size(); j++) {
			sum += arr[i][j];
		}
		minSum = min(minSum, sum);
	}
	return minSum;
}

vector<bool> visited;

void Back_Tracking(int size) {
	if (size == rotateArr2.size()) {
		resultMinSize = min(resultMinSize, getMinRowSum());
		return;
	}

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

		if (visited[i] == true)continue;
		visited[i] = true;

		vector<vector<int>> copyArr = arr;

		Node node = rotateArr2[i];
		int leftSero = node.sero - node.S;
		int leftGaro = node.garo - node.S;
		int rightSero = node.sero + node.S;
		int rightGaro = node.garo + node.S;
	
		rotateArr(leftSero, leftGaro, rightSero, rightGaro);

		Back_Tracking(size + 1);
	
		arr = copyArr;
		visited[i] = false;
	}
}

void Game_Start() {
	
	visited.resize(rotateArr2.size(), false);
	Back_Tracking(0);
	cout << resultMinSize;
}

int main(void) {
	Input();
	Game_Start();
}