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

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

17406번: 배열 돌리기 4

<풀이>

1. 배열 정보와 회전 정보를 입력받는다.

2. 회전순서를 정해서 배열을 돌리고, 얻을 수 있는 배열의 최솟값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 회전 순서에 따라 배열이 다 달라지므로, 모든 경우의 회전순서를 다 만들어서 시뮬레이션을 진행해야합니다. 따라서, 저는 브루트포스를 선택하였습니다.

 

2. 시뮬레이션 구현하기

=> 회전순서를 정했으면, 시뮬레이션을 진행해야합니다. 시뮬레이션의 핵심은 문제의 조건에 맞는 정확한 구현입니다. 저는 배열을 돌릴때 Deque을 사용했습니다.

 

3. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다. 모든 경우의 회전순서를 만든다.

(2) 회전순서를 정했으면, 시뮬레이션을 진행한다.(배열을 돌릴 때 덱을 사용한다)

(3) 배열의 최솟값을 return한다.

자세한 구현은 아래 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <deque>
#define INF 987654321
 
using namespace std;
 
int N, M, K;
int A[51][51];
int A_copy[51][51];
int R[6], C[6], S[6];
int order[6];
bool visited[6];
int answer;
 
void rotate(int x1, int y1, int x2, int y2) {
    deque<int> dq;
    //숫자 담기
    for (int i = y1; i < y2; i++) dq.push_back(A_copy[x1][i]);
    for (int i = x1; i < x2; i++) dq.push_back(A_copy[i][y2]);
    for (int i = y2; i > y1; i--) dq.push_back(A_copy[x2][i]);
    for (int i = x2; i > x1; i--) dq.push_back(A_copy[i][y1]);
    //순서 바꾸기
    dq.push_front(dq.back());
    dq.pop_back();
    //숫자 순서대로 놓기
    for (int i = y1; i < y2; i++) {
        A_copy[x1][i] = dq.front(); dq.pop_front();
    }
    for (int i = x1; i < x2; i++) {
        A_copy[i][y2] = dq.front(); dq.pop_front();
    }
    for (int i = y2; i > y1; i--) {
        A_copy[x2][i] = dq.front(); dq.pop_front();
    }
    for (int i = x2; i > x1; i--) {
        A_copy[i][y1] = dq.front(); dq.pop_front();
    }
}
 
void copyA() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            A_copy[i][j] = A[i][j];
        }
    }
}
 
void simulation() {
    //1. 맵 복사
    copyA();
    //2. 순서에 따라 배열 돌리기
    for (int i = 0; i < K; i++) {
        int o = order[i];
        int r = R[o], c = C[o], s = S[o];
        for (int j = 0; j < s; j++) {
            rotate(r - s + j, c - s + j, r + s - j, c + s - j);
        }
    }
}
 
int rowSum(int col) {
    int output = 0;
    for (int i = 1; i <= M; i++) {
        output += A_copy[col][i];
    }
    return output;
}
 
int minRowSum() {
    int output = INF;
    for (int i = 1; i <= N; i++) {
        output = min(output, rowSum(i));
    }
    return output;
}
 
int selectOperOrder(int cnt) {
    if (cnt == K) {
        simulation();
        return minRowSum();
    }
 
    int ret = INF;
    for (int i = 0; i < K; i++) {
        if (!visited[i]) {
            visited[i] = true;
            order[cnt] = i;
            ret = min(ret, selectOperOrder(cnt + 1));
            visited[i] = false;
        }
    }
    return ret;
}
 
void solution() {
    answer = selectOperOrder(0);
}
 
int main() {
    //초기화
    N = 0, M = 0, K = 0;
    memset(A, 0, sizeof(A));
    memset(R, 0, sizeof(R));
    memset(C, 0, sizeof(C));
    memset(S, 0, sizeof(S));
    memset(order, 0, sizeof(order));
    memset(visited, false, sizeof(visited));
    answer = 0;
 
    //입력
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < K; i++) {
        cin >> R[i] >> C[i] >> S[i];
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.