3085번

3085번 - 사탕 게임

완전 탐색을 통해서 문제를 풀었다. 

두점을 바꾼 새로운 맵을 구하는 함수 - select 함수

새로운 맵에서 가로(행) , 세로(열) 을 탐색하면서 최대값을 찾는 함수 - search

그리고 중복해서 탐색되는 값을 없애기 위해서 오른쪽과 아래만 찾아가면서 select 함수를 호출했다.

어차피 2중 for문을 통해서 오른쪽 먼저, 그 다음 아래로 움직이기 때문이다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<char>> map(51, vector<char>(51));
int ans = 0;
int dx[2] = { 0,1 };
int dy[2] = { 1,0 };
int n;
void search(vector<vector<char>> &map2)
{
    int ans1 = 0;
    int ans2 = 0;
    //가로
    for (int i = 0; i < n; i++)
    {
        int tmp = 1;
        char a = map2[i][0];
        for (int j = 1; j < n; j++)
        {
            if (map2[i][j] == a)
            {
                tmp++;
                a = map2[i][j];
            }
            else
            {
                tmp = 1;
                a = map2[i][j];
            }
 
            ans1 = max(ans1, tmp);
            
        }
    }
    //세로
    for (int i = 0; i < n; i++)
    {
        int tmp = 1;
        char a = map2[0][i];
        for (int j = 1; j < n; j++)
        {
            if (map2[j][i] == a)
            {
                tmp++;
                a = map2[j][i];
            }
            else
            {
                tmp = 1;
                a = map2[j][i];
            }
 
            ans2 = max(ans2, tmp);
 
        }
    }
 
    ans = max({ ans,ans1, ans2 });
}
void select(int x,int y)
{
    for (int d = 0; d < 2; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if (nx >= 0 && ny >= 0 && nx < n && ny < n)
        {
            vector<vector<char>> map2 = map;
 
            char tmp = map2[x][y];
            map2[x][y] = map2[nx][ny];
            map2[nx][ny] = tmp;
 
            search(map2);
        }
 
    }
 
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        char tmp[51];
        scanf("%s", &tmp);
        for (int j = 0; j < n; j++)
        {
            map[i][j] = tmp[j];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            select(i, j);
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}