[Algorithm] BOJ 17406 배열 돌리기 4

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

17406 배열 돌리기 4

---

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

출력

배열 A의 값의 최솟값을 출력한다.

예제

---

풀이

---

생각

• 회전에 대한 부분만 잘 구현하면 되는 문제라고 생각한다.
  • 이전에 회전을 풀다가 토나온 적이 있어서 굳이 점화식을 생각하지 않고, 일단 노가다 방법으로라도 시계 방향으로 돌아가는 방법을 생각하려 했다.
• 앞선 여러 문제에서 백트랙킹의 구조에 대해 알아볼 수 있었다.
  • 앞선 문제들에서는 백트랙킹의 과정 속에서 필요없는 추가 연산을 제거해야하는 경우도 존재했으나, 이 경우에는 선택하는 최대 경우가 6개 밖에 없어 경우의 수가 많지 않았다. 고로, 백트랙킹의 구조는 기본 구조만을 사용해도 될 것이라 생각했다.

방법

• 백트랙킹으로 회전 연산의 순서를 정해준다.
  • 먼저, 회전을 수행하기 전에 Original 배열 oriA을 회전을 수행할 배열 A로 복사해준다. Original 배열에 회전을 수행하면, 다음 회전 순서 경우의 수에서 Original 배열이 없어 잘못된 값을 계산하므로.
  • K개를 다 고른 경우 (회전 순서를 다 정한 경우), 회전을 수행한다.
• 회전은 저장해놓은 순서대로 진행.
• 회전을 완료하고선, 배열의 값. 즉, 배열 행의 합의 최소값을 계산하고, 지금까지의 최소값과 비교하여 조건에 맞는 경우 업데이트.

유의

• 딱히 유의할 점은 없다.
• 회전 코드를 구현 시 집중해서 구현할 것.
• 최종 값을 처음 초기화할 때, 모든 경우에 발생할 수 있는 수보다 크게 초기화해놔야 한다.
  • 이 문제의 경우, M이 최대 50이고 배열 요소 값이 최대 100이므로 최대 행의 값이 5000이다.
  • 고로, 처음에 5000보다 큰 값으로 초기화해놔야 한다.

---

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#define SIZE 51
#define bb ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
int N, M, K, res = 10'000;
int oriA[SIZE][SIZE], A[SIZE][SIZE], B[7][3];
bool check[7];
vector<int> vec;

void rotate(int r, int c, int s) {
    for (int i = 1; i <= s; ++i) {
        int last = A[r - i + 1][c - i];
        int new_r = r - i + 1;
        int new_c = c - i;

        // 시계방향 회전
        while (r + i > new_r) {
            A[new_r][new_c] = A[new_r + 1][new_c];
            new_r++;
        }
        while (c + i > new_c) {
            A[new_r][new_c] = A[new_r][new_c + 1];
            new_c++;
        }
        while (new_r > r - i) {
            A[new_r][new_c] = A[new_r - 1][new_c];
            new_r--;
        }
        while (new_c > c - i) {
            A[new_r][new_c] = A[new_r][new_c - 1];
            new_c--;
        }
        A[new_r][new_c] = last;
    }
}

void solution(int cnt) {
    if (cnt == K) { // 회전 방법 다 고른 경우

        copy(&oriA[0][0], &oriA[0][0] + SIZE * SIZE, &A[0][0]); // 회전 시뮬레이션을 위해 복사

        // 고른 회전 방법 다 수행
        for (int i = 0; i < K; ++i) {
                // 회전 보낼 때, 행과 열에 -1 주고 보내야 함.
            rotate(B[vec[i]][0] - 1, B[vec[i]][1] - 1, B[vec[i]][2]); 
        }

        // 배열의 값 (행의 합의 최소값 계산 및 비교)
        for (int i = 0; i < N; ++i) {
            int rsum = 0;
            for (int j = 0; j < M; ++j) {
                rsum += A[i][j];
            }
            res = min(res, rsum);
        }

        return;
    }

    // selecting
    for (int i = 0; i < K; ++i) {
        if (check[i]) continue;
        vec.push_back(i);
        check[i] = true;
        solution(cnt + 1);
        vec.pop_back();
        check[i] = false;
    }
}

int main()
{
    // input
    cin >> N >> M >> K;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> oriA[i][j];
        }
    }
    for (int i = 0; i < K; ++i) {
        cin >> B[i][0] >> B[i][1] >> B[i][2];
    }

    // play
    solution(0);

    cout << res << '\n';
    return 0;
}

---

느낀점

• 오랜만에 오류없이 한 번에 풀었고, 30분도 안걸린 것 같다.
• 백트랙킹에 대해 좀 이해도가 많이 오른 것 같다.
• 회전이 토가 나오지만, 천천히 집중해서 수행할 생각하면 오류없이 구현해낼 수 있을 것 같다!

---

참조

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