알고리즘/Backjoon

[C] 3085 - 사탕 게임

ShinDongJun 2019. 12. 4. 22:30

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

 

3085번: 사탕 게임

문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하

www.acmicpc.net

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<string.h>
#define max(A, B) (A > B ? A : B)
 
char arr[55][55];
int len;
int MAX = 1;
 
void check();
void swap(char *p, char *q);
 
int main(void)
{
    int n;
    int max = -1, tmp;
    int i, j;
    scanf("%d",&n);
    len = n;
    for(i = 0; i < n; ++i)
        scanf("%s",arr[i]);
 
    for(i = 0; i < len; ++i)
    {
        for(j = 0; j < len - 1; ++j)
        {
            if(arr[i][j] != arr[i][j+1])
            {
                swap(&arr[i][j], &arr[i][j+1]);
                check();
                swap(&arr[i][j], &arr[i][j+1]);
            }
            if(arr[j][i] != arr[j+1][i])
            {
                swap(&arr[j][i], &arr[j+1][i]);
                check();
                swap(&arr[j][i], &arr[j+1][i]);    
            }
        }
    }
    printf("%d\n", MAX);
 
    return 0;
}
 
void swap(char *p, char *q)
{
    char tmp = *p;
    *p = *q;
    *q = tmp;
}
 
void check()
{
    int count = 1;
    //양 옆
    for (int i = 0; i < len; i++)
    {
        count = 1;
        for (int j = 1; j < len; j++)
        {
            if (arr[i][j - 1] == arr[i][j])
                count++;
            else
            {
                MAX = max(MAX, count);
                count = 1;
            }
        }
        MAX = max(MAX, count);
    }
    
    //위 아래
    for (int i = 0; i < len; i++)
    {
        count = 1;
        for (int j = 0; j < len - 1; j++)
        {
            if (arr[j + 1][i] == arr[j][i])
                count++;
            else
            {
                MAX = max(MAX, count);
                count = 1;
            }
        }
        MAX = max(MAX, count);
    }
}