[브루트포스] BOJ 3085 사탕게임

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

3085번: 사탕 게임

- 문제 접근

4종류의 사탕이 NxN의 배열에 존재할 때,인접한 한 쌍의 사탕을 바꿔서 상하 또는 좌우로 가장 긴 사탕의 개수를 구한다.

0. 초기값에서 중복되는 사탕의 개수 중 최대값 저장

1. bfs와 같은 원리로 인접한 사탕이 다른 위치를 큐로 저장

2. 큐를 돌면서 상하좌우에 자신과 다른 사탕이 있으면 바꿈

3. 바꾼 열과 행을 확인하여 중복되는 사탕의 개수 확인

4. 3에서 얻은 값의 최대값과 0번의 최대값 비교

5. 1~4 반복해서 최대값을 출력

 

 

- 정답

(중복되는 코드는 함수로 만들자)

#include "bits/stdc++.h"

using namespace std;

char arr[55][55];
//int check[55][55];
char check[2][55];



int n;

int main()
{
    
    int dx[] = { 0,0,1,-1 };
    int dy[] = { 1,-1,0,0 };

    cin >> n;

    queue<pair<int, int>> q;
    int ans = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];

            if (arr[i][j - 1] != arr[i][j] ||
                arr[i - 1][j] != arr[i][j])
            {
                q.push({ i,j });
            }


        }
    }

    int xcmp = 0;
    int ycmp = 0;

    int nxcmp = 0;
    int nycmp = 0;

    for (int i = 0; i < n; i++)
    {
        ycmp = 0;
        xcmp = 0;
        memset(check, 0, 55*2);

        for (int j = 0; j < n; j++)
        {


            check[0][j] = arr[i][j];
            check[1][j] = arr[j][i];
            if (j > 0)
            {
                if (check[0][j] == check[0][j - 1]) // 가로            
                    xcmp++;
                
                else
                    xcmp = 0;

                nxcmp = max(xcmp, nxcmp);

                if (check[1][j] == check[1][j - 1]) // 세로
                    ycmp++;
                else
                    ycmp = 0;

                nycmp = max(ycmp, nycmp);
            }
            

        }

        int tmp = max(ycmp+1, xcmp+1);

        ans = max(ans, tmp);

    }
    
    memset(check, 0, 55*2);

    while (!q.empty())
    {
        int nx = q.front().first;
        int ny = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int x = nx + dx[i];
            int y = ny + dy[i];
            if (x < 0 || y < 0) continue;
            if (x >= n || y >= n) continue;
  
            if (arr[nx][ny] == arr[x][y]) continue;

            xcmp = 0;
            ycmp = 0;

            nxcmp = 0;
            nycmp = 0;

            // 바꾸기
            char sztmp = arr[nx][ny];
            arr[nx][ny] = arr[x][y];
            arr[x][y] = sztmp;

            // 개수 체크
            for (int k = 0; k < n; k++)
            {
                check[0][k] = arr[x][k];
                check[1][k] = arr[k][y];
                if (k > 0)
                {
                    if (check[0][k] == check[0][k - 1]) // 가로
                        xcmp++;
                    else
                        xcmp = 0;
                    
                    nxcmp = max(xcmp, nxcmp);


                    if (check[1][k] == check[1][k - 1]) // 세로
                        ycmp++;

                    else
                        ycmp = 0;

                    nycmp = max(ycmp, nycmp);

                }

            }

            //원복
            sztmp = arr[x][y];
            arr[x][y] = arr[nx][ny];
            arr[nx][ny] = sztmp;


            int tmp = max(nycmp +1, nxcmp +1);

            ans = max(ans, tmp);

            memset(check, 0, 55*2);
        }

    }
    
    cout << ans;
}