백준 온라인 저지(BOJ) 3085번 - 사탕 게임

백준 온라인 저지(BOJ) 3085번 - 사탕 게임

경우의 수

1. NxN 크기의 테이블에 사탕이 있다 (N < 50)
2. 인접한 두 칸을 고르고, 사탕을 교환한다 -> (N^2) * 2 의 경우의 수 (정확히는 (N-1)^2 * 2)
   • 처음 고른 칸의 오른쪽, 아래쪽을 인접한 칸이라고 가정
3. 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고름 -> O(N^2)

해답

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int check(vector<string> &a){
   int n = a.size();
   int ans = 1;
   for(int i=0; i<n; i++){
       int cnt = 1;
       for(int j=1; j<n; j++){
           if(a[i][j] == a[i][j-1])
               cnt += 1;
           else
               cnt = 1;
           if(ans < cnt)
               ans = cnt;
       }
       cnt = 1;
       for(int j=1; j<n; j++){
           if(a[j][i] == a[j-1][i])
               cnt += 1;
           else
               cnt = 1;
           if(ans < cnt)
               ans = cnt;
       }
   }
   return ans;
}

int main() {
    int n;
    cin >> n;
    vector<string> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(j+1 < n){
                swap(a[i][j], a[i][j+1]);
                int temp = check(a);
                if(ans < temp)
                    ans = temp;
                swap(a[i][j], a[i][j+1]);
            }
            if(i+1 < n){
                swap(a[i][j], a[i+1][j]);
                int temp = check(a);
                if(ans < temp)
                    ans = temp;
                swap(a[i][j], a[i+1][j]);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• 2번까지의 과정이 swap 함수까지이다. (STL 기본 함수)

• swap은 오른쪽 값과 교환 / 아래 값과 교환으로 나누어서 진행한다.

• 3번을 수행하기 위해 check 함수로 들어간다.

• check 함수에서 각 행/열에 대해 연속된 최대 길이를 계산한다.

• 계산 결과를 temp로 받아 최대 값일 경우 ans를 갱신한다.