백준 3085번 - 사탕게임

전략: brute force

 

N×N크기의테이블에사탕이있다.(N≤50)
인접한두칸을고르고,사탕을교환한다. (N의 제곱)
그다음,같은색으로이루어져있는가장긴연속부분행또는열을고르는문제 (N의 네제곱)

 

더 좋은 알고리즘: 자기가 건든 열과 행만 바꾼다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int check(vector<string> colors){
  int answer = 1;
  int size = colors.size();

  for(int i = 0; i<size; i++){
    int count = 1;
    for(int j = 1; j<size ; j++){
       if (colors[i][j] == colors[i][j-1]) {
                count += 1;
            } else {
                count = 1;
            }
            if (answer < count) answer = count;
    }

    count = 1;
    for(int j = 1; j<size ; j++){
       if (colors[j][i] == colors[j-1][i]) {
                count += 1;
            } else {
                count = 1;
            }
            if (answer < count) answer = count;
    }

  }

  return answer;
}

int main() {
  int n;
  cin >> n;
    
  vector<string> colors(n);
  for (int i=0; i<n; i++) {
    cin >> colors[i];
  }

  int answer = 0;

  for(int i = 0; i<n; i++){
    for(int j = 0; j<n; j++){
      if(j+1<n){
        swap(colors[i][j], colors[i][j+1]);
        int temp = check(colors);
        if(temp>answer) answer = temp;
        swap(colors[i][j],colors[i][j+1]);
      }

      if(i+1<n){
        swap(colors[i][j], colors[i+1][j]);
        int temp = check(colors);
        if(temp>answer) answer = temp;
        swap(colors[i][j],colors[i+1][j]);
      }

    }
  }
  
  cout << answer << endl;
  return 0;
}