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();
}
'백준 > 구현' 카테고리의 다른 글
백준 18808 c++ "스티커 붙이기" -PlusUltraCode- (0) | 2025.07.10 |
---|---|
백준 16637 c++ "괄호 추가하기" -PlusUltraCode- (0) | 2025.07.07 |
백준 17140 c++ "이차원 배열과 연산" -PlusUltraCode- (0) | 2025.07.02 |
백준 2580 c++ "스도쿠" -PlusUltraCode- (0) | 2025.06.16 |
백준 21608 c++ "상어 초등학교" -PlusUltraCode- (0) | 2025.06.03 |