백준 문제풀이 - 17406 번

링크 -> https://www.acmicpc.net/problem/17406

1. 요약 및 풀이방법

2차원 배열의 회전 공식에 따라 배열을 가능한 모든 경우에 대해 회전시킨다.
이때, 배열의 최솟값을 구하는 문제이다.

회전 배열이 여러개인 경우,
회전변환 순서에 따라 배열의 결과가 달라진다. (행렬곱처럼)

즉, Arr 배열과 r1, r2의 회전 배열이 있을 때,
Arr -> r1 -> r2 변환의 결과와
Arr -> r2 -> r1 변환의 결과는 다르다.

따라서 이 문제를 해결하기 위해 회전배열에 대한 순열 알고리즘이 필요하다. (순서에 의존)

문제 풀이 요약은 다음과 같다.

• 모든 회전배열을 원소로 갖는 g_rotate 벡터를 순열 알고리즘을 통해 모든 경우를 순회시킨다.
  (아래의 solution, rotateArr 함수)
• g_rotate의 각 회전 배열에 대한 회전변환을 g_arr배열에 순서대로 적용시킨다.
  (아래의 rotateArr, rotate 함수)
• 하나의 순서조합에 대한 변환이 끝나면 g_arr배열의 배열값을 구해 최솟값을 저장한다.
  (아래의 get_arr_value 함수)

2. Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <limits>

int g_row, g_col, g_rotate_trial, g_answer = std::numeric_limits<int>::max();
std::vector<std::vector<int> > g_arr;
std::vector<std::vector<int> > g_rotate;

void input()
{
    std::cin >> g_row >> g_col >> g_rotate_trial;

    g_arr.reserve(g_row);
    for (int i = 0; i < g_row; i++)
    {
        std::vector<int> tmp_vec(g_col);
        for (int j = 0; j < g_col; j++)
        {
            int tmp;
            std::cin >> tmp;
            tmp_vec[j] = tmp;
        }
        g_arr.push_back(tmp_vec);
    }

    g_rotate.reserve(g_rotate_trial);
    for (int i = 0; i < g_rotate_trial; i++)
    {
        std::vector<int> tmp_vec(3);
        for (int j = 0; j < 3; j++)
        {
            int tmp;
            std::cin >> tmp;
            tmp_vec[j] = tmp;
        }
        g_rotate.push_back(tmp_vec);
    }
}

void get_arr_value(std::vector<std::vector<int> > rotated_arr)
{
    int tmp;

    for (size_t i = 0; i < rotated_arr.size(); i++)
    {
        tmp = std::accumulate(rotated_arr[i].begin(), rotated_arr[i].end(), 0);
        if (tmp < g_answer)
            g_answer = tmp;
    }
}

void rotate(std::vector<std::vector<int> > &arr, std::vector<int> r_arr)
{
    int row = r_arr[0] - 1, col = r_arr[1] - 1;

    for (int distance = 1; distance <= r_arr[2]; distance++)
    {
        int push;
        int pop = 0;
        for (int j = col - distance; j <= col + distance; j++)
        {
            push = arr[row - distance][j];
            arr[row - distance][j] = pop;
            pop = push;
        }
        for (int i = row - distance + 1; i <= row + distance; i++)
        {
            push = arr[i][col + distance];
            arr[i][col + distance] = pop;
            pop = push;
        }
        for (int j = col + distance - 1; j >= col - distance; j--)
        {
            push = arr[row + distance][j];
            arr[row + distance][j] = pop;
            pop = push;
        }
        for (int i = row + distance - 1; i >= row - distance; i--)
        {
            push = arr[i][col - distance];
            arr[i][col - distance] = pop;
            pop = push;
        }
    }
}

void rotateArr(std::vector<std::vector<int> > current_rotate_set)
{
    std::vector<std::vector<int> > rotated_arr = g_arr;
    for (size_t i = 0; i < current_rotate_set.size(); i++)
    {
        rotate(rotated_arr, current_rotate_set[i]);
    }
    get_arr_value(rotated_arr);
}

void solution()
{
    std::sort(g_rotate.begin(), g_rotate.end());
    do
    {
        rotateArr(g_rotate);
    } while (std::next_permutation(g_rotate.begin(), g_rotate.end()));
}

int main()
{
    input();
    solution();
    std::cout << g_answer << std::endl;
}

3. 학습 내용

• 순열 알고리즘을 직접 구현하는 방법도 있지만, 위의 과제에서는 cpp에서 제공하는 next_permutation함수를 사용했다.
  next_permutation함수를 쓰기 전, sort로 정렬하는 코드를 볼 수 있는데,
  data가 오름차순이어야 next_permutation함수가 올바르게 작동하기 때문이다.
  이후에는 do-while구문을 사용하여 모든 경우에 대한 로직을 실행시켜주면 된다.
  추후에 순열 알고리즘에 대한 로직을 직접 작성해 볼 계획이다.

• 생각보다 rotate함수 구현에 시간이 오래걸렸다.
  직접 index를 생각하면서 하나하나 구현하다보니 헷갈리는 부분이 많았는데,
  더 좋은 방법이 있는지 고민 해봐야할듯!

4. 결과