[PS] 백준 17406번 배열 돌리기 4

박상혁·2026년 7월 27일
순열완전 탐색

PS

목록 보기
91/97

이번에는 백준 17406번 배열 돌리기 4 문제를 풀어보았습니다.

이 문제는 주어진 회전 연산을 모두 한 번씩 수행하되, 연산 순서를 자유롭게 정할 수 있습니다.

회전 연산의 순서에 따라 최종 배열이 달라지므로, 가능한 모든 연산 순서를 확인한 뒤 배열의 값이 가장 작아지는 경우를 찾아야 합니다.

따라서 순열을 이용한 완전탐색과 배열 시뮬레이션으로 해결하였습니다.

문제 설명

N × M 크기의 배열 A가 주어집니다.

배열의 값은 각 행의 합 중 최솟값입니다.

회전 연산 (r, c, s)는 중심 (r, c)를 기준으로 크기가 다른 여러 개의 테두리를 각각 시계 방향으로 한 칸씩 이동시키는 연산입니다.

주어진 K개의 회전 연산은 모두 한 번씩 사용해야 하며, 수행 순서는 자유롭게 정할 수 있습니다.

가능한 모든 연산 순서 중 배열의 값을 최소로 만드는 경우를 구하는 문제입니다.

풀이 아이디어

회전 연산의 개수 K는 최대 6입니다.

따라서 가능한 연산 순서의 수는 최대

6! = 720

개입니다.

next_permutation()을 사용하여 모든 연산 순서를 생성하고, 각 순서에 대해 실제로 배열을 회전시킵니다.

하나의 회전 연산 (r, c, s)는 중심에서 거리가 1인 테두리부터 s인 테두리까지 총 s개의 층으로 구성됩니다.

각 층마다 다음 순서로 테두리 좌표를 벡터에 저장합니다.

  1. 위쪽 변
  2. 오른쪽 변
  3. 아래쪽 변
  4. 왼쪽 변

좌표를 시계 방향 순서로 저장한 뒤, 현재 좌표의 값을 다음 좌표로 이동시키면 테두리가 시계 방향으로 한 칸 회전합니다.

모든 연산을 수행한 뒤 각 행의 합을 구하고, 그중 최솟값으로 정답을 갱신합니다.

코드

#include <bits/stdc++.h>
using namespace std;
int A[101][101];
int N,M,C;
int rotate_input[6][3];
int ret = INT_MAX;

void run_rotate(int y, int x, int n){
    int temp1[101][101];
    for (int i=1; i<=n; i++) {
        memcpy(temp1, A, sizeof(A));
        int top = y-i;
        int bot = y+i;
        int left = x-i;
        int right = x+i;
        vector<pair<int, int>> idx;
        for (int j=left; j<=right; j++)
            idx.push_back({top,j});
        for (int j=top+1; j<=bot; j++)
            idx.push_back({j,right});
        for (int j=right-1; j>=left; j--)
            idx.push_back({bot,j});
        for (int j=bot-1; j>top; j--)
            idx.push_back({j,left});

        int idx_size = idx.size();
        for (int j=0; j<idx_size; j++) {
            int cy = idx[j].first;
            int cx = idx[j].second;

            int ny = idx[(j+1)%idx_size].first;
            int nx = idx[(j+1)%idx_size].second;

            temp1[ny][nx] = A[cy][cx];
        }
    }
    memcpy(A, temp1, sizeof(A));
}
void get_min_val() {
    for (int i=1; i<=N; i++) {
        int sum=0;
        for (int j=1; j<=M; j++) {
            sum += A[i][j];
        }
        ret = min(ret, sum);
    }
}
void solve(vector<int> order) {
    int temp1[101][101];
    memcpy(temp1, A, sizeof(A));
    for (int i=0; i<order.size(); i++) {
        run_rotate(rotate_input[order[i]][0], rotate_input[order[i]][1],rotate_input[order[i]][2]);
    }
    get_min_val();
    memcpy(A, temp1, sizeof(A));
}
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> M >> C;

    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            cin >> A[i][j];
        }
    }

    vector<int> permute_vec(C);
    for (int i=0; i<C; i++) {
        cin >> rotate_input[i][0];
        cin >> rotate_input[i][1];
        cin >> rotate_input[i][2];
        permute_vec[i] = i;
    }

    do {
        solve(permute_vec);
    } while(next_permutation(permute_vec.begin(), permute_vec.end()));

    cout << ret;
    return 0;
}

풀이 흐름

  1. 배열과 회전 연산 정보를 입력받습니다.

  2. 각 회전 연산의 번호를 permute_vec에 저장합니다.

  3. next_permutation()을 사용하여 가능한 모든 연산 순서를 생성합니다.

  4. 각 순열마다 현재 배열을 임시 배열에 저장합니다.

  5. 해당 순서대로 모든 회전 연산을 수행합니다.

  6. 회전이 끝난 배열에서 각 행의 합을 계산합니다.

  7. 행의 합 중 최솟값으로 ret을 갱신합니다.

  8. 다음 순열을 확인하기 위해 배열을 원래 상태로 복구합니다.

  9. 모든 순서를 확인한 뒤 ret을 출력합니다.

구현 포인트

1. 회전 연산 정보 저장

int rotate_input[6][3];

각 행에는 하나의 회전 연산 정보를 저장합니다.

rotate_input[i][0] = r
rotate_input[i][1] = c
rotate_input[i][2] = s

K가 최대 6이므로 크기를 6으로 선언하였습니다.

2. 연산 순서를 순열로 생성

vector<int> permute_vec(C);

permute_vec에는 회전 연산의 인덱스를 저장합니다.

for (int i=0; i<C; i++) {
    ...
    permute_vec[i] = i;
}

예를 들어 회전 연산이 3개라면 초기 상태는 다음과 같습니다.

0 1 2

이후 next_permutation()을 사용하여 모든 순서를 확인합니다.

do {
    solve(permute_vec);
} while(next_permutation(permute_vec.begin(), permute_vec.end()));

회전 연산은 수행 순서에 따라 결과가 달라지므로 모든 순열을 탐색해야 합니다.

3. 순열마다 배열 복구

void solve(vector<int> order) {
    int temp1[101][101];
    memcpy(temp1, A, sizeof(A));

각 순열은 반드시 같은 초기 배열에서 시작해야 합니다.

따라서 회전 연산을 수행하기 전에 현재 배열을 temp1에 저장합니다.

for (int i=0; i<order.size(); i++) {
    run_rotate(rotate_input[order[i]][0],
               rotate_input[order[i]][1],
               rotate_input[order[i]][2]);
}

전달받은 순서대로 모든 회전 연산을 수행합니다.

모든 연산과 최솟값 계산이 끝난 후에는 배열을 다시 복구합니다.

memcpy(A, temp1, sizeof(A));

이렇게 해야 다음 순열도 원본 배열에서 시작할 수 있습니다.

4. 하나의 회전 연산을 여러 층으로 나누기

for (int i=1; i<=n; i++)

회전 연산 (y, x, n)은 중심을 기준으로 총 n개의 테두리를 회전시킵니다.

예를 들어 n = 2라면 다음 두 층을 각각 회전합니다.

중심에서 거리 1인 테두리
중심에서 거리 2인 테두리

현재 층의 거리를 i라고 했을 때 범위는 다음과 같습니다.

int top = y-i;
int bot = y+i;
int left = x-i;
int right = x+i;

이를 통해 현재 회전시킬 정사각형 테두리의 위, 아래, 왼쪽, 오른쪽 범위를 구합니다.

5. 테두리 좌표를 시계 방향으로 저장

vector<pair<int, int>> idx;

현재 층의 테두리 좌표를 시계 방향 순서대로 저장합니다.

위쪽 변

for (int j=left; j<=right; j++)
    idx.push_back({top,j});

왼쪽 위에서 오른쪽 위까지 저장합니다.

오른쪽 변

for (int j=top+1; j<=bot; j++)
    idx.push_back({j,right});

위쪽 모서리는 이미 저장했으므로 top + 1부터 시작합니다.

아래쪽 변

for (int j=right-1; j>=left; j--)
    idx.push_back({bot,j});

오른쪽 아래 모서리는 이미 저장했으므로 right - 1부터 왼쪽 방향으로 저장합니다.

왼쪽 변

for (int j=bot-1; j>top; j--)
    idx.push_back({j,left});

아래쪽과 위쪽 모서리는 이미 저장했으므로 두 모서리를 제외합니다.

이 과정을 거치면 테두리의 모든 좌표가 중복 없이 시계 방향 순서로 저장됩니다.

6. 다음 좌표로 값 이동

int idx_size = idx.size();
for (int j=0; j<idx_size; j++) {

현재 좌표의 값을 다음 좌표로 이동시킵니다.

int cy = idx[j].first;
int cx = idx[j].second;

현재 위치를 가져옵니다.

int ny = idx[(j+1)%idx_size].first;
int nx = idx[(j+1)%idx_size].second;

다음 위치는 j + 1번째 좌표입니다.

마지막 좌표의 다음 위치는 첫 번째 좌표가 되어야 하므로 % idx_size를 사용합니다.

temp1[ny][nx] = A[cy][cx];

현재 좌표의 값을 다음 좌표에 저장합니다.

테두리 좌표가 시계 방향 순서로 저장되어 있으므로, 모든 값이 시계 방향으로 한 칸씩 이동합니다.

7. 회전 중 임시 배열을 사용하는 이유

회전할 때 값을 원본 배열에 바로 덮어쓰면 아직 이동하지 않은 원래 값이 사라질 수 있습니다.

따라서 각 층을 회전하기 전에 현재 배열을 임시 배열에 복사합니다.

memcpy(temp1, A, sizeof(A));

값을 이동할 때는 원본 배열 A에서 읽고, 임시 배열 temp1에 씁니다.

temp1[ny][nx] = A[cy][cx];

이렇게 하면 모든 좌표가 회전 전 상태의 값을 기준으로 이동합니다.

8. 여러 층을 순서대로 회전

for (int i=1; i<=n; i++) {
    memcpy(temp1, A, sizeof(A));

현재 코드에서는 안쪽 층부터 바깥쪽 층까지 순서대로 회전합니다.

각 층은 서로 겹치지 않는 테두리이므로 순서대로 처리해도 문제가 없습니다.

한 층의 회전 결과는 temp1에 저장됩니다.

다음 층을 처리할 때는 다시 현재 배열 상태를 기준으로 복사합니다.

모든 층의 회전이 끝난 후 최종 결과를 원본 배열에 반영합니다.

memcpy(A, temp1, sizeof(A));

9. 배열의 값 계산

void get_min_val() {
    for (int i=1; i<=N; i++) {
        int sum=0;

각 행의 합을 구합니다.

for (int j=1; j<=M; j++) {
    sum += A[i][j];
}

현재 행의 합을 구한 뒤 정답과 비교합니다.

ret = min(ret, sum);

모든 행을 확인하면 현재 배열의 값인 행 합의 최솟값이 ret에 반영됩니다.

10. 1-based 인덱스 사용

문제에서 주어지는 회전 연산의 좌표는 1부터 시작합니다.

코드에서도 배열을 다음과 같이 사용합니다.

for (int i=1; i<=N; i++) {
    for (int j=1; j<=M; j++) {

따라서 입력 좌표를 별도로 0-based로 변환하지 않고 그대로 사용할 수 있습니다.

int top = y-i;
int bot = y+i;
int left = x-i;
int right = x+i;

문제의 (r, c, s) 값을 그대로 사용하여 회전 범위를 계산할 수 있다는 장점이 있습니다.

11. 완전탐색이 가능한 이유

회전 연산의 개수는 최대 6입니다.

따라서 가능한 연산 순서의 수는 최대 다음과 같습니다.

6! = 720

각 순서에 대해 모든 회전 연산을 수행하고 배열의 값을 계산해도 경우의 수가 충분히 작습니다.

따라서 모든 순열을 확인하는 완전탐색으로 해결할 수 있습니다.

시간복잡도

회전 연산의 순서 수는 K!개입니다.

하나의 순열마다 K개의 회전 연산을 수행합니다.

회전 연산 하나는 최악의 경우 배열의 테두리들을 순회하므로 O(N × M)으로 볼 수 있습니다.

모든 연산이 끝난 뒤 행의 합을 계산하는 데에도 O(N × M)이 필요합니다.

따라서 전체 시간복잡도는 다음과 같습니다.

O(K! × K × N × M)

K는 최대 6이므로 충분히 해결할 수 있습니다.

profile
박상혁
엉덩이로 성장하는 개발자
이전 포스트

[PS] 백준 3190번 뱀

다음 포스트

[PS] 백준 15662번 톱니바퀴 (2)

0개의 댓글