3085 사탕게임

사탕 게임

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	4387	1352	1027	31.551%

문제

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

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

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

입력

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

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

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

출력

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

파이썬으로 풀다가 계속 이상해서 c++로 풀었다.

머릿속으로는 생각이 되나 직접구현하는것이 개인적으로 까다로웠다.

#include "pch.h"

#include <iostream>

#include <string>

using namespace std;

#pragma warning(disable : 4996)

int n;

int check(char** mtx);

int main()

{

    ios::sync_with_stdio(false);

    freopen( "input.txt", "r", stdin);

    

    cin >> n;

    char** mtx = new char*[n];

    

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

        

        string a;

        cin >> a;

        

        mtx[i] = new char[n];

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

            mtx[i][j] = a.at(j);

        }

        

    }

    int answer = 0;

    int tmp;

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

    {

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

        {

            

            //스왑

            char temp = mtx[i][j];

            mtx[i][j] = mtx[i][j + 1];

            mtx[i][j + 1] = temp;

            //체크

            tmp=check(mtx);

            answer = answer > tmp ? answer : tmp;

            //복구

            temp = mtx[i][j];

            mtx[i][j] = mtx[i][j + 1];

            mtx[i][j + 1] = temp;

            //스왑

            temp = mtx[j][i];

            mtx[j][i] = mtx[j+1][i];

            mtx[j+1][i] = temp;

            //체크

            tmp = check(mtx);

            answer = answer > tmp ? answer : tmp;

            //복구

            temp = mtx[j][i];

            mtx[j][i] = mtx[j + 1][i];

            mtx[j + 1][i] = temp;

        }

        

    }

    

    cout << answer;

    

    return 0;

}

int check(char** mtx) {

    int max_cnt = 0;

    int cnt = 1;

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

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

            if (mtx[i][j] == mtx[i][j - 1]) {

                cnt++;

            }

            else {

                max_cnt = cnt > max_cnt ? cnt : max_cnt;

                cnt = 1;

            }

        }

        max_cnt = cnt > max_cnt ? cnt : max_cnt;

        cnt = 1;

    }

    cnt = 1;

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

        cnt = 1;

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

            if (mtx[j][i] == mtx[j - 1][i]) {

                cnt++;

            }

            else {

                max_cnt = cnt > max_cnt ? cnt : max_cnt;

                cnt = 1;

            }

        }

        max_cnt = cnt > max_cnt ? cnt : max_cnt;

    }

        

    

    return max_cnt;

}