[ SWEA 1216 ] 회문2 (C++)

SWExpertAcademy의 회문2(1216 / D3) 문제이다.

[ 문제풀이 ]

1) 이 글을 읽기전에, 회문1(1215)을 풀어보지 않았거나, 이 글에 대한 풀이글을 읽고 오지 않았다면

   먼저 읽고 오는것을 권장한다. 왜냐하면 회문(1215) 풀이와 굉장히 비슷해서 회문(1215)풀이에서 말했던 중복된

   내용들에 대해서는 이 글에서는 설명하지 않을 것이다.

   [ 회문1(1215) 풀이 바로가기 ]

   회문1과 같이 모든 좌표에서 탐색을 하는 방법을 동일하다. 하지만, 회문1과 달리 이 문제에서는 회문의 길이가

   정해져있지 않다. 또한, 최대 회문의 길이를 구해야 하는 문제이다.

   그래서 회문1과 같이, 모든 좌표에서 탐색 + 탐색 가능 한 모든 길이 탐색 이 2가지를 모두 탐색해 주었다.

   회문인지 아닌지 판단하는 방법은 회문1의 풀이와 동일하며, 모든 길이를 탐색하는 부분을 위해서 반복문을

   하나 더 추가해 주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int Answer;
char MAP[MAX][MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 1;
    memset(MAP, 0, sizeof(MAP));
}
 
void Input()
{
    int N; cin >> N;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Check_Garo(int x, int y, int Len)
{
    int sx = x;
    int sy = y;
    int ex = x;
    int ey = y + Len - 1;
    bool Flag = false;
 
    while (1)
    {
        if (sy > ey)
        {
            Flag = true;
            break;
        }
 
        if (MAP[sx][sy] == MAP[ex][ey])
        {
            sy++;
            ey--;
        }
        else break;
        
    }
    if (Flag == true) Answer = Bigger(Answer, Len);
}
 
void Check_Sero(int x, int y, int Len)
{
    int sx = x;
    int sy = y;
    int ex = x + Len - 1;
    int ey = y;
    bool Flag = false;
 
    while (1)
    {
        if (sx > ex)
        {
            Flag = true;
            break;
        }
 
        if (MAP[sx][sy] == MAP[ex][ey])
        {
            sx++;
            ex--;
        }
        else break;
    }
 
    if (Flag == true) Answer = Bigger(Answer, Len);
}
 
void Solution()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            for (int k = 2; k < MAX; k++)
            {
                if (j + k <= MAX) Check_Garo(i, j, k);
                if (i + k <= MAX) Check_Sero(i, j, k);
            }
        }
    }
}
 
void Solve()
{
    int Tc = 10;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}