[백준] C++ 알고리즘 3085번 - 사탕 게임 문제

문제

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

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int check(vector<string>& a) {
    int n = a.size();
    int ans = 0;
    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() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,ans=0;
    cin >> n;
    vector<string> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j + 1 < n) {
                swap(v[i][j], v[i][j + 1]);
                int temp = check(v);
                if (ans < temp) ans = temp;
                swap(v[i][j + 1], v[i][j]);
            }
            if (i + 1 < n) {
                swap(v[i][j], v[i + 1][j]);
                int temp = check(v);
                if (ans < temp)ans = temp;
                swap(v[i + 1][j], v[i][j]);
            }
        }
    }
    cout << ans;
}

풀이

전체의 경우의수를 다 생각해봐야 문제를 해결 할 수 있다.

우선 인접한 색깔을 서로 바꿔서 그 바꾼 상태에서의 연속된 색이 최대인 것들을 찾는 문제이다.

우선 메인문에서 인접한 색을 바꾼후 체크 함수에서 같은색이 연속으로 행 열 중 어디가 최대인지 검사한다.