BOJ 3085 - 사탕 게임

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

3085번: 사탕 게임

 

이 문제는 주의할것이 한가지 있는데,

DFS 같은 방식으로 푸는 문제가 아니다.

 

브루트포스 방식으로 풀어야 하는데,

 

1. 양옆으로 자리를 바꿨을 때,

2. 위아래로 자리를 바꿨을 때

 

이 두가지 경우를 고려하면서 코드를 작성해야 한다.

 

또한 사탕의 갯수를 고려할때,

가로로 계산했을때 최대 몇개인지

세로로 계산했을때 최대 몇개인지를 따져야한다

다만 주의 할 것은 행,열을 빙고처럼 완성하는게 아니라

그냥 한 행/열 에서 최대 일치 하는 사탕 갯수 몇개인지 따지는 것 뿐이다.

 

그리고 마지막으로 

자리를 바꾼 다음에 최대 갯수를 계산한 후, 다시 자리를 바꿔서 원래 행렬 모양으로 돌려 놓아야 한다.

그래야 다음 번째에서 정확한 계산을 할 수 있기 때문이다.

 

- c++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int N;
int answer;
 
int max_cnt(vector<string>& vec_str) {
    int vec_len = vec_str.size();
    int result = 1;
 
    // 행으로 탐색
    for (int i = 0; i < vec_len; i++) {
        int cnt = 1;
        int str_len = vec_str[i].length();
        for (int j = 0; j < str_len - 1; j++) {
            if (vec_str[i][j] == vec_str[i][j + 1]) {
                cnt++;
            } else {
                result = max(result, cnt);
                cnt = 1;
            }
        }
        result = max(result, cnt);
    }
 
    // 열로 탐색
    for (int i = 0; i < vec_len; i++) {
        int cnt = 1;
        int str_len = vec_str[i].length();
        for (int j = 0; j < str_len - 1; j++) {
            if (vec_str[j][i] == vec_str[j + 1][i]) {
                cnt++;
            } else {
                result = max(result, cnt);
                cnt = 1;
            }
        }
        result = max(result, cnt);
    }
 
    return result;
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> N;
 
    vector<string> in_str;
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        in_str.push_back(str);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N - 1; j++) {
            // 양옆 변화
            swap(in_str[i][j], in_str[i][j + 1]);
            answer = max(answer, max_cnt(in_str));
            swap(in_str[i][j], in_str[i][j + 1]);  // 행렬 원상 복귀
 
            // 위아래 변화
            swap(in_str[j][i], in_str[j + 1][i]);
            answer = max(answer, max_cnt(in_str));
            swap(in_str[j][i], in_str[j + 1][i]);  // 행렬 원상 복귀
        }
    }
 
    printf("%d", answer);
 
    return 0;
}