/ 알고리즘

사탕 게임

알고리즘 무차별 대입 acmicpc.net coci
https://4am.kr/candy-game/
시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB290886133.152%

문제

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

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

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

입력

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

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

출력

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

예제 입력

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력

4

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 1번

나의 접근방법

나의 전략

접근 방식은 유사했지만, 사탕을 바꾸어서(SWAP) 세는 방식의 문제로, 다른 풀이를 참조하였다.

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 105;

//캔디가 들어 있는 배열
char a[MAXN][MAXN];
//배열의 크기
int n;

// 각 행(열)에서 최대 캔디 갯수 찾기
int maxniz() {
    // 최대 갯수
    int best = 0;
    //배열의 크기만큼 반복문을 돈다
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j ) {
            //c1 = 열 방향으로(x 방향, 옆 쪽) 갈 때 최대 사탕 갯수
            //c2 = 행 방향으로(y 방향, 아래 쪽) 갈 때 최대 사탕 갯수
            //x = 행 방향의 임시 좌표
            //y = 열 방향의 임시 좌표
            int c1 = 0, c2 = 0, x = i, y = j;
            //1. 배열 범위를 벗어나지 않고 && 사탕이 있는 경우 -> 2. 열 방향으로 한 칸 이동, c1++ 열 방향의 임시 사탕갯수 증가
            while( x < n && a[x][j] == a[i][j] ) x++, c1++;
            //1. 배열 범위를 벗어나지 않고 && 사탕이 있는 경우 -> 2. 행 방향으로 한 칸 이동, c2++ 행 방향의 임시 사탕갯수 증가
            while( y < n && a[i][y] == a[i][j] ) y++, c2++;
            //우선 c1, c2를 비교하여 임시 최대 값 중 최대 값을 찾아내고,
            //원래의 최대 값과 비교해 갱신한다.
            best = max( best, max(c1,c2) );
        }
    //최대 값을 리턴
    return best;
}

int main( void ) {
    
    // 입력받을 배열의 행과 열의 크기를 입력받는다.
    scanf( "%d", &n );
    
    // 배열을 입력받는다.
    for( int i = 0; i < n; ++i )
        scanf( "%s", a[i] );
    
    //rj = (최종) 캔디의 최대 갯수
    int rj = 0;
    
    //전체 사탕이 들어있는 배열을 모두 탐색한다.
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j ) {
            //1. 열 방향 기준좌표(i)를 +1 한다
            //2. 기준좌표가 배열의 범위를 벗어나지 않고(바운더리 체크) &&
            //   사탕이 한 쪽이 없는 경우
            if( i+1 < n && a[i][j] != a[i+1][j] ) {
                //3. 원래 칸(i,j)과 기준좌표(옆 칸)(i+1,j)의 내용물을 바꿔본다.(SWAP)
                swap( a[i][j], a[i+1][j] );
                //4. 캔디 갯수를 다시 세서 최대값을 갱신한다.
                rj = max( rj, maxniz() );
                //5. 내용물의 위치([i+1,j] -> [i,j])를 원상복귀한다.
                swap( a[i][j], a[i+1][j] );
            }
            //1. 열 방향 기준좌표(j)를 +1 한다
            //2. 기준좌표가 배열의 범위를 벗어나지 않고(바운더리 체크) &&
            //   사탕이 한 쪽이 없는 경우
            if( j+1 < n && a[i][j] != a[i][j+1] ) {
                //3. 원래 칸(i,j)과 기준좌표(옆 칸)(i,j+1)의 내용물을 바꿔본다.(SWAP)
                swap( a[i][j], a[i][j+1] );
                //4. 캔디 갯수를 다시 세서 최대값을 갱신한다.
                rj = max( rj, maxniz() );
                //5. 내용물의 위치([i,j+1] -> [i,j])를 원상복귀한다.
                swap( a[i][j], a[i][j+1] );
            }
        }
    //최대 캔디 갯수를 출력한다.
    printf( "%d\n", rj);
    return 0;
}
나의 코드
/* acmicpc.net 3085 사탕 게임
https://www.acmicpc.net/problem/3085
*/
#include <iostream>
using namespace std;
#define MAX 50
#define SWAP(A,B){ int TMP = A; A = B; B = TMP;}

int box[MAX + 1][MAX + 1] = { 0 };
int max_candy = 0;
int N = 0;

void input()
{
    //RED(C)=>1, YELLOW(Y)=>2, GREEN(Z)=>3, BLUE(P)=>4
    char C;
    int color = 0;
    cin >> N;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            cin >> C;
            switch (C) {
                case 'C':
                    color = 1; break;
                case 'Y':
                    color = 2; break;
                case 'Z':
                    color = 3; break;
                case 'P':
                    color = 4; break;
                default:
                    color = 0; break;
            }
            box[i][j] = color;
        }
}

bool check(int n){ return N >= n; }
int maxval(int a, int b){ return a > b ? a : b;}

int maxcount()
{
    int max = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            int x = i, y = j, maxicandy = 0, maxjcandy = 0;
            while(box[i][j] == box[x][j] && check(x)) x++, maxicandy++;
            while(box[i][j] == box[i][y] && check(y)) y++, maxjcandy++;
            max = maxval(max, maxval(maxicandy, maxjcandy));
        }
    return max;
}

void solve()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
        {
            if(box[i+1][j] != box[i][j] && check(i+1))
            {
                SWAP(box[i+1][j], box[i][j]);
                max_candy = maxval(max_candy, maxcount());
                SWAP(box[i+1][j], box[i][j]);
            }
            
            if(box[i][j+1] != box[i][j] && check(j+1))
            {
                SWAP(box[i][j+1],box[i][j]);
                max_candy = maxval(max_candy, maxcount());
                SWAP(box[i][j+1],box[i][j]);
            }
        }
}

void print()
{
    cout << max_candy << endl;
}

int main()
{
    input();
    solve();
    print();
    
    return 0;
}