[백준]: 3085번: 사탕게임 / 완전 탐색(Brute-force Search)

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

해당문제의 핵심은 

1. 상근이는 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. (Swap한다)

2. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. (행, 열에 대해서 가장 긴 길이를 구한다).

이 두가지를 생각하면 깊게 어렵지 않다. 

#include<iostream>

using namespace std;

#include<algorithm>

int n,cnt;

char candy[51][51];

int ans = 0;

void check()

{

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

{

cnt = 1;

for (int j = 2; j <= n; j++)

{

if (candy[i][j - 1] == candy[i][j])

{

cnt++;

}

else

{

ans = max(ans, cnt);

cnt = 1;

}

}

ans = max(ans, cnt);    //이 부분이 필요한 이유는 -> n=3, YYY일떄 저 부분이 없다면 0이 된다. (Why? else을 지나지 않게 되기떄문에 ans변경x

}// garo

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

{

cnt = 1;

for (int j = 2; j <= n; j++)

{

if (candy[j-1][i] == candy[j][i])

{

cnt++;

}

else

{

ans = max(ans, cnt);

cnt = 1;

}

}

ans = max(ans, cnt);

}

//sero

}

int main()

{

cin >> n;

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

{

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

{

cin >> candy[i][j];

}

}

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

{

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

{

if ((j + 1) <= n)

{

swap(candy[i][j], candy[i][j + 1]);

check();

swap(candy[i][j], candy[i][j + 1]);

}

if ((i + 1) <= n)

{

swap(candy[i][j], candy[i + 1][j]);

check();

swap(candy[i][j], candy[i + 1][j]);

}

}

}// 행에대해서 swap하고 한번쭉 돌리고, 열에 대해서 swap하고 한번 쭉 돌리고

cout << ans << endl;

return 0;

}