3085번 사탕 게임

문제 링크

사탕 게임

문제 풀이

N * N 크기의 판에 색이 다른 인접한 사탕끼리 바꾼 다음, 모두 같은 색으로 이루어진 가장 긴 연속 행이나 열의 길이를 구하는 문제이다.
N의 크기가 50 이하이고, 인접한 사탕끼리 교환할 수 있는 경우는 모두 50 * 49 * 2번이다. 따라서 완전 탐색으로 푼다. 바꾼 열과 행에서 가장 긴 연속 부분을 찾으면 된다. 이때, 바꾼 열과 행에서만 찾으면 되도록 같은 색깔의 사탕이라도 교환하도록 구현한다.

구현

#include <iostream>
#include <algorithm>
using namespace std;

int N;
char board[51][51];

int check(int row1, int col1, int row2, int col2) {
    int ret = 0, len = 1;

    for (int i = 0; i < N - 1; ++i) {
        if (board[row1][i] == board[row1][i + 1]) ++len;
        else len = 1;
        ret = max(ret, len);
    }
    len = 1;
    for (int i = 0; i < N - 1; ++i) {
        if (board[row2][i] == board[row2][i + 1]) ++len;
        else len = 1;
        ret = max(ret, len);
    }
    len = 1;
    for (int i = 0; i < N - 1; ++i) {
        if (board[i][col1] == board[i + 1][col1]) ++len;
        else len = 1;
        ret = max(ret, len);
    }
    len = 1;
    for (int i = 0; i < N - 1; ++i) {
        if (board[i][col2] == board[i + 1][col2]) ++len;
        else len = 1;
        ret = max(ret, len);
    }
    return ret;
    
int solve() {
    int ret = -1;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            swap(board[i][j], board[i][j + 1]);
            ret = max(ret, check(i, j, i, j + 1));
            swap(board[i][j], board[i][j + 1]);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            swap(board[j][i], board[j + 1][i]);
            ret = max(ret, check(j, i, j + 1, i));
            swap(board[j][i], board[j + 1][i]);
        }
        
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> board[i];

    cout << solve();
    return 0;
}