[백준/구현/백트래킹/C++] 17406번 배열 돌리기 4 (삼성 코딩테스트)

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

17406번: 배열 돌리기 4

문제 해결 방법

1. 회전연산의 순서 정하기 (수열 : 백트래킹)

2. 회전연산 구현 (재귀)

3. 배열 A의 값 구하기

크게 3가지로 나눌 수 있다.

 

먼저 회전 연산의 순서를 정하기 위해 백트래킹을 이용했다.

// 회전연산 순서 정하기
void setOrder(int cnt){
    if(cnt == K){
        solve();
        return;
    }
    for(int i=0; i<K; i++){
        if(!isVisit[i]){
            isVisit[i] = true;
            arr[cnt] = i;
            setOrder(cnt+1);
            isVisit[i] = false;
        }
    }
}

 

순서가 구해지면 회전 연산을 수행해야 하는데 

경우의 수가 여러번이기 때문에 배열 A를 바로 사용하지 않고 copyA라는 배열을 만들어서 사용한다.

회전 연산은 s부터 시작해서 s가 1이 될때까지 돌리고 0이 되면 리턴하는 재귀함수로 구현했다.

// 회전연산
void operateCircle(int r, int c, int s){

    if(s==0) return;
    // 위 가로줄
    int tmp1 = copyA[r-s][c+s];
    for(int i=c+s; i>c-s; i--){
        copyA[r-s][i] = copyA[r-s][i-1];
    }
    // 오른쪽 세로줄
    int tmp2 = copyA[r+s][c+s];
    for(int i=r+s; i>r-s; i--){
        copyA[i][c+s] = copyA[i-1][c+s];
    }
    copyA[r-s+1][c+s] = tmp1;
    // 밑 가로줄
    int tmp3 = copyA[r+s][c-s];
    for(int i=c-s; i<c+s; i++){
        copyA[r+s][i] = copyA[r+s][i+1];
    }
    copyA[r+s][c+s-1] = tmp2;
    // 왼쪽 세로줄
    for(int i=r-s; i<r+s; i++){
        copyA[i][c-s] = copyA[i+1][c-s];
    }
    copyA[r+s-1][c-s] = tmp3;
    // printCopyA();
    operateCircle(r, c, s-1);
}

회전연산이 끝나면 배열 A를 구하고 최소값을 구한다

 

전체 코드

#include <bits/stdc++.h>


using namespace std;

int N, M, K;
int A[51][51];
int copyA[51][51];
int opCircle[6][3]; // r, c, s (r-s, c-s) ~ (r+s, c+s)
int arr[6];
bool isVisit[6];
int answer = 2e9;

void printCopyA(){
    cout << endl;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            cout << copyA[i][j];
        }
        cout << endl;
    }
}

// 배열 A 복사
void copyMap(){
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            copyA[i][j] = A[i][j];
        }
    }
}

// 배열 A 값 구하기
int findArrA(){

    int result = 2e9;
    for(int i=1; i<=N; i++){

        int cnt = 0;
        for(int j=1; j<=M; j++){
            cnt += copyA[i][j];
        }
        result = min(result,cnt);
    }

    return result;
}

// 회전연산
void operateCircle(int r, int c, int s){

    if(s==0) return;
    // 위 가로줄
    int tmp1 = copyA[r-s][c+s];
    for(int i=c+s; i>c-s; i--){
        copyA[r-s][i] = copyA[r-s][i-1];
    }
    // 오른쪽 세로줄
    int tmp2 = copyA[r+s][c+s];
    for(int i=r+s; i>r-s; i--){
        copyA[i][c+s] = copyA[i-1][c+s];
    }
    copyA[r-s+1][c+s] = tmp1;
    // 밑 가로줄
    int tmp3 = copyA[r+s][c-s];
    for(int i=c-s; i<c+s; i++){
        copyA[r+s][i] = copyA[r+s][i+1];
    }
    copyA[r+s][c+s-1] = tmp2;
    // 왼쪽 세로줄
    for(int i=r-s; i<r+s; i++){
        copyA[i][c-s] = copyA[i+1][c-s];
    }
    copyA[r+s-1][c-s] = tmp3;
    // printCopyA();
    operateCircle(r, c, s-1);
}

void solve(){
    int result;
    copyMap();
    for(int i=0; i<K; i++){
        int x = arr[i]; // i번째 회전연산 수행
        int r = opCircle[x][0];
        int c = opCircle[x][1];
        int s = opCircle[x][2];

        operateCircle(r,c,s);
    }
    result = findArrA();
    answer = min(answer, result);
}

// 회전연산 순서 정하기
void setOrder(int cnt){
    if(cnt == K){
        solve();
        return;
    }
    for(int i=0; i<K; i++){
        if(!isVisit[i]){
            isVisit[i] = true;
            arr[cnt] = i;
            setOrder(cnt+1);
            isVisit[i] = false;
        }
    }
}

void input(){
    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 >> opCircle[i][0] >> opCircle[i][1] >> opCircle[i][2];
    }
}

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

    input();
    setOrder(0);
    cout << answer;

    return 0;
}