[BOJ 3085] 사탕 게임

1) 문제 링크

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

2) 접근

완전탐색 문제라고 해서 봤는데, 인접한 칸끼리 바꾸는 경우의 수에 지도를 탐색하는 경우의 수를 곱해봤더니 정도. 1억 번 안 넘으니까 대충 가능할 거 같다는 생각에 있는 그대로 구현했다.

3) 풀이

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

int N;
char candy[50][50];

int MaxCandy(){
    int result = 0, cnt;
    for(int i=0; i<N; ++i){
        cnt = 1;
        for(int j=0; j<N-1; ++j){
            if(candy[i][j] == candy[i][j+1]){
                ++cnt;
            }
            else{
                if(result < cnt) { result = cnt; }
                cnt = 1;
            }
        }
        if(result < cnt) { result = cnt; }
    }
    for(int j=0; j<N; ++j){
        cnt = 1;
        for(int i=0; i<N-1; ++i){
            if(candy[i][j] == candy[i+1][j]){
                ++cnt;
            }
            else{
                if(result < cnt) { result = cnt; }
                cnt = 1;
            }
        }
        if(result < cnt) { result = cnt; }
    }
    return result;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            cin >> candy[i][j];
        }
    }

    int res, temp;

    res = MaxCandy();
    for(int i=0; i<N; ++i){
        for(int j=0; j<N-1; ++j){
            if(candy[i][j] != candy[i][j+1]){
                swap(candy[i][j], candy[i][j+1]);

                temp = MaxCandy();
                if(res < temp) { res = temp; }

                swap(candy[i][j], candy[i][j+1]);
            }
        }
    }

    for(int i=0; i<N-1; ++i){
        for(int j=0; j<N; ++j){
            if(candy[i][j] != candy[i+1][j]){
                swap(candy[i][j], candy[i+1][j]);

                temp = MaxCandy();
                if(res < temp) { res = temp; }

                swap(candy[i][j], candy[i+1][j]);
            }
        }
    }

    cout << res;

    return 0;
}

4) 피드백

당연히 최적해는 아니라고 생각했다. O(N^2)짜리로 최적인 문제는 이 정도 난이도에서는 많지 않으므로…
우선 0ms가 뜬 3304184번 코드를 보자. 기본적인 접근 자체에는 큰 차이가 없다. 그러나 인접한 사탕들의 최대 개수를 구하는 함수가 재귀를 이용했다는 점에서 내 코드에 비해 시간복잡도를 떨어뜨릴 수 있었던 것 같다. 차차 읽어봐야지.