[3085] 사탕 게임(C++)

문제

[3085] 사탕 게임

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

 

 

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

 

 

내 코드(C++)

// [3085] 사탕 게임
// https://www.acmicpc.net/problem/3085
// 브루트포스

#include <iostream>
#include <algorithm> // swap
using namespace std;

int n, ans = 0; // 보드의 크기, 정답
char board[51][51];

// 행 비교(한 줄)
void checkRow(int x)
{   
    int cnt = 1;
    char compare = board[x][0];
    for(int i = 1 ; i < n ; i++) {
        if(board[x][i] == compare) cnt++;
        else {
            cnt = 1;
            compare = board[x][i];
        } 
        if(cnt > ans) ans = cnt;
    }
}

// 열 비교(한 줄)
void checkCol(int y)
{
    int cnt = 1;
    char compare = board[0][y];
    for(int i = 1 ; i < n ; i++) {
        if(board[i][y] == compare) cnt++;
        else {
            cnt = 1;
            compare = board[i][y];
        }
        if(cnt > ans) ans = cnt;
    }
}

int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < n ; j++) {
            cin >> board[i][j];
        }
    }

    // 인접한 두 수가 다른 경우만 swap하면 처음부터 한 줄이 다 같은 경우는 보지 못하게 됨
    // 교환이 일어난 행, 열만 비교
    for(int i = 0 ; i < n-1 ; i++) {
        for(int j =  0 ; j < n-1 ; j++) {
            // 양 옆
            swap(board[i][j], board[i][j+1]);
            checkRow(i); checkCol(j); checkCol(j+1);
            swap(board[i][j], board[i][j+1]);

            // 위아래
            swap(board[i][j], board[i+1][j]);
            checkRow(i); checkRow(i+1); checkCol(j);
            swap(board[i][j], board[i+1][j]);
        }
    }
    // 맨 마지막 행
    for(int j = 0 ; j < n-1 ; j++) {
        swap(board[n-1][j], board[n-1][j+1]);
        checkRow(n-1); checkCol(j); checkCol(j+1);
        swap(board[n-1][j], board[n-1][j+1]);
    }

    cout << ans << '\n';
}