[ 백준 16926 ] 배열 돌리기1 (C++)

백준의 배열돌리기(16926) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 문제는 쉽다.. 구현이 생각보다 어려워서 그렇지...

   먼저 몇 개의 좌표에서 사각형을 돌려줘야 되는지 생각해보자.

  

   먼저 위와 같은 예를 한번 봐보도록 하자.

   왼쪽부터 차례대로 맵의 크기가 4x4 , 6x4, 4x6 짜리 맵들이다.

   위의 맵들은 검은점으로 표시된 사각형, 파랑점으로 표시된 사각형 총 2군데에서 배열을 돌려줘야 한다는 것을

   알 수 있다.

  

   그렇다면 위의 맵을 하번 봐보자. 위의 맵에서는 검정, 파랑, 빨강 3개의 사각형을 돌려줘야 한다는 것을 알 수 있다.

   그렇다면 몇 개의 사각형을 돌려야 되는지는 어떻게 구해야 할까 ??

   바로 가로길이와 세로길이 중 더 짧은 변의 길이 / 2이 그 갯수이다.

   다시 첫번째 예로 가보자. 4x6, 6x4, 4x6 공통점이 모두 더 짧은 변의 길이가 '4'라는 것이다. 

   4를 2로 나눠버리면 2가 나오는데, 이 2의 의미는 '2개의 사각형을 돌려야한다' 라는 것을 의미한다.

   그 아래의 사각형을 예로 들면 8x6짜리 사각형이다. 즉, 6 / 2 = 3이 되고, 이는 3개의 사각형을 돌려줘야 한다는 것을

   의미한다.

   그럼 홀수가 나오면 어떻게 할까요 ?? 그럴 리 없다. 왜냐하면 문제의 제한에 주어져 있다.

   두 변의 길이중 더 짧은 길이는 2로 나누어 떨어진다 라고 !

   그럼 그 사각형들의 시작점을 어떻게 구할까?? 본인은 이렇게 계산해주었다.

   가장 왼쪽 위의 점을 (0, 0)으로 봤을 때, (0, 0), (1, 1), (2, 2) .... 이 좌표들이 돌려야 될 사각형의 시작점으로

   잡고 생각해주었다.

   실제로 돌려주는 것은 각 좌표마다 재귀를 통해서 R번 움직일 때 까지 구현해 주었다. 이 과정에서 방향의 개념도

   사용하였다.

   왜냐하면 본인은 4개의 변을 따로따로 돌려주었기 때문이다.

   4개의 변이라고 하는 것은, 돌려야 할 사각형에서 왼쪽 세로 변, 아래쪽 가로변, 오른쪽 세로변, 위쪽 가로변

   이렇게 4개의 변을 의미하는데, 왼쪽 세로변의 첫 진행방향은 남쪽, 아래 가로변의 첫 진행방향은 동쪽,

   오른쪽 세로변의 첫 진행방향은 북쪽, 위쪽 가로변의 첫 진행방향은 서쪽이 된다.

   따라서, 배열의 범위를 벗어나게 되면, 방향을 그때그때 바꿔주면서 총 R번 돌때까지 재귀로 깊게 들어가도록

   구현해 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 300
using namespace std;
 
int N, M, R, Rotate_Pos;
int MAP[MAX][MAX], C_MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
void Input()
{
    cin >> N >> M >> R;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }    
}
 
void DFS(int x, int y, int dir, int r, int Range, int Orig)
{
    if (r == R)
    {
        C_MAP[x][y] = Orig;
        return;
    }
 
    if (dir == 0)        // Move East
    {
        if (y + 1 < M - Range) DFS(x, y + 1, dir, r + 1, Range, Orig);
        else DFS(x - 1, y, 3, r + 1, Range, Orig);    
    }
    else if (dir == 1)    // Move West
    {
        if (y - 1 >= Range) DFS(x, y - 1, dir, r + 1, Range, Orig);
        else DFS(x + 1, y, 2, r + 1, Range, Orig);
    }
    else if (dir == 2)    // Move South
    {
        if (x + 1 < N - Range) DFS(x + 1, y, dir, r + 1, Range, Orig);
        else DFS(x, y + 1, 0, r + 1, Range, Orig);
    }
    else if (dir == 3)    // Else
    {
        if (x - 1 >= Range) DFS(x - 1, y, dir, r + 1, Range, Orig);
        else DFS(x, y - 1, 1, r + 1, Range, Orig);
    }
}
 
void Solution()
{
    if (N > M) Rotate_Pos = M / 2;
    else Rotate_Pos = N / 2;
 
    for (int RP = 0; RP < Rotate_Pos; RP++)
    {
        int x = RP;
        int y = RP;
 
        for (int i = x; i < N - RP; i++)
        {
            if (Visit[i][y] == false)
            {
                DFS(i, y, 2, 0, RP, MAP[i][y]);
                Visit[i][y] = true;
            }
        }
        for (int i = y; i < M - RP; i++)
        {
            if (Visit[N - 1 - RP][i] == false)
            {
                DFS(N - 1 - RP, i, 0, 0, RP, MAP[N - 1 - RP][i]);
                Visit[N - 1 - RP][i] = true;
            }
        }
        for (int i = N - 1 - RP; i >= RP; i--)
        {
            if (Visit[i][M - 1 - RP] == false)
            {
                DFS(i, M - 1 - RP, 3, 0, RP, MAP[i][M - 1 - RP]);
                Visit[i][M - 1 - RP] = true;
            }
        }
        for (int i = M - 1 - RP; i >= RP; i--)
        {
            if (Visit[x][i] == false)
            {
                DFS(x, i, 1, 0, RP, MAP[x][i]);
                Visit[x][i] = true;
            }
        }
    }
    
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cout << C_MAP[i][j] << " ";
        }
        cout << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}