[백준][브루트 포스] 사탕 게임

1. 문제 주소

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

3085번: 사탕 게임

2. 문제

Y	C	P	Z	Y
C	Y	Z	Z	P
C	C	P	P	P
Y	C	Y	Z	C
C	P	P	Z	Z

다음과 같이 사탕이 배치되어 있을 때 가장 긴 연속 부분의 사탕 수를 구하는 candy_num 함수를 작성을 하였다. 먼저 각 행을 돌면서 기준이 되는 사탕의 오른쪽과 같은지를 확인하여 연속 부분의 길이를 구하였다. 그러고 나서 각 열을 돌면서 아래쪽의 사탕과 같은지 확인하여 연속 부분의 길이를 구하여 둘 중 큰 값을 return 하도록 코드를 구성하였다.

main 함수에는 swap을 이용하여 한개의 이웃한 사탕을 교환 후 candy_num 함수를 이용하여 가장 긴 연속 부분의 길이를 구하도록 코드를 작성하였다.

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int candy_num(vector<string>& candyboard) {
    int n = candyboard.size();
    int max_num = 1;
    for (int i = 0; i < n; i++) {
        int candy_count = 1;
        for (int j = 0; j < n - 1; j++) {
            if (candyboard[i][j] == candyboard[i][j + 1]) {
                candy_count += 1;
            }
            else candy_count = 1;
            if (candy_count > max_num)
                max_num = candy_count;
        }
 
        candy_count = 1;
        for (int k = 0; k < n - 1; k++) {
            if (candyboard[k][i] == candyboard[k + 1][i]) {
                candy_count += 1;
            }
            else candy_count = 1;
            
            if (candy_count > max_num)
                max_num = candy_count;
        }
    }
    return max_num;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<string> candyboard(n);
 
    for (int i = 0; i < n; i++)
        cin >> candyboard[i];
    int max_num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            swap(candyboard[i][j], candyboard[i][j + 1]);
            if (max_num < candy_num(candyboard))
                max_num = candy_num(candyboard);
            swap(candyboard[i][j], candyboard[i][j + 1]);
        }
        for (int k = 0; k < n - 1; k++) {
            swap(candyboard[k][i], candyboard[k + 1][i]);
            if (max_num < candy_num(candyboard))
                max_num = candy_num(candyboard);
            swap(candyboard[k][i], candyboard[k + 1][i]);
        }
    }
    cout << max_num << '\n';
    return 0;    
}