[Algorithm]Baekjoon 17406번 :: 배열 돌리기 4

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
struct RotateInfo
{
    int r, c, s;
};
 
int n, m, k;
int arr[53][53] = { 0 };
int tempArr[53][53] = { 0 };
int dirs[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
 
vector<RotateInfo> rotateInfos; 
vector<int> indices;
 
bool visited[7] = { false };
int answer = 0x3f3f3f3f;
 
 
bool IsInRange(int cy, int cx, int sy, int sx, int dy, int dx)
{
    if (cy < sy || cy > dy) return false;
    if (cx < sx || cx > dx) return false;
 
    return true;
}
 
void Rotate(const RotateInfo& rotateInfo)
{
    int sy = rotateInfo.r - rotateInfo.s;
    int sx = rotateInfo.c - rotateInfo.s;
    int dy = rotateInfo.r + rotateInfo.s;
    int dx = rotateInfo.c + rotateInfo.s;
 
 
    while (sy < dy && sx < dx) // 바깥쪽부터 회전.
    {
        int cy = sy;
        int cx = sx;
        int prevNum = tempArr[cy][cx];
        tempArr[cy][cx] = 0;
        
 
        for (int i = 0; i < 4; ++i)
        {
            while (1) // 한방향 끝까지 쭈욱
            {
                int ny = cy + dirs[i][0];
                int nx = cx + dirs[i][1];
 
                if (!IsInRange(ny, nx, sy, sx, dy, dx))
                {
                    break;
                }
 
                int nextNum = tempArr[ny][nx];
                tempArr[ny][nx] = prevNum;
                prevNum = nextNum;        
 
                cy = ny;
                cx = nx;
            }
        }
 
        ++sy;
        ++sx;
        --dy;
        --dx;
    }
}
 
 
void GetMinRowSum()
{
 
    memcpy(tempArr, arr, sizeof(arr));
 
    
    for (int i = 0; i < indices.size(); ++i)
    {
        int index = indices[i];
 
        Rotate(rotateInfos[index]);
    }
 
    // 최솟값 구하기
    for (int i = 1; i <= n; ++i)
    {
        int sum = 0;
 
        for (int j = 1; j <= m; ++j)
        {
            sum += tempArr[i][j];
        }
 
        answer = min(answer, sum);
    }
}
 
void DFS()
{
    if (indices.size() == k)
    {
        GetMinRowSum();
 
        return;
    }
 
 
    for (int i = 0; i < rotateInfos.size(); ++i)
    {
        if (visited[i]) continue;
 
        visited[i] = true;
        indices.push_back(i);
 
        DFS();
 
        visited[i] = false;
        indices.pop_back();
    }
 
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
 
    for (int i = 0; i < k; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        rotateInfos.push_back({ a,b,c });
    }
 
    DFS();
 
    cout << answer;
}
 
 

 

 

 

수열로 경우의 수를 뽑고 그거에 따라 배열을 회전을 시키는 문제.

이런 시뮬레이션 문제를 좋아하지 않아서 좀 외면하는 경향이 있긴 한데.. 한번쯤은 풀어놔야 할 것 같아서 해봤다.

실제 회전하는 코드만 인덱스 안헷갈리게 주의하면 되고, 이외에는 경우의 수 뽑기정도?