[3085번] 사탕 게임

문제

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

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

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

입력

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

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

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

출력

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

나의 답

#include <bits/stdc++.h>

using namespace std;

// global variable
int N;
int** table;

// Function
void Input(void) {
    scanf("%d", &N);

    table = new int*[N];
    for(int i = 0; i < N; ++i) {
        table[i] = new int[N];
    }

    char input;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            scanf("%c", &input);
            while(input != 'C' && input != 'P' && input != 'Z' && input != 'Y') {
                scanf("%c", &input);
            }

            if (input == 'C')
                table[i][j] = 0;
            else if(input == 'P')
                table[i][j] = 1;
            else if(input == 'Z')
                table[i][j] = 2;
            else if(input == 'Y')
                table[i][j] = 3;
        }
    }
}

int CalculateResult() {
    int result = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            int cur_result = 1;

            int temp_i = i;
            int temp_j = j;

            for(cur_result = 1; temp_i+1 < N && table[temp_i][j] == table[temp_i+1][j]; temp_i++, cur_result++);
            result = max(result, cur_result);

            for(cur_result = 1; temp_j+1 < N && table[i][temp_j] == table[i][temp_j+1]; temp_j++, cur_result++);
            result = max(result, cur_result);
        }
    }

    return result;
}

int Calculate(void) {
    int result = 0;

    // 인접한 것 교환
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            if(i+1 < N && table[i][j] != table[i+1][j]) {
                swap(table[i][j], table[i+1][j]);
                result = max(result, CalculateResult());
                swap(table[i][j], table[i+1][j]);
            }
            if(j+1 < N && table[i][j] != table[i][j+1]) {
                swap(table[i][j], table[i][j+1]);
                result = max(result, CalculateResult());
                swap(table[i][j], table[i][j+1]);
            }
        }
    }

    return result;
}

int main(void) {
    Input();
    int result = Calculate();

    printf("%d\n", result);
}