[백준/BOJ] 3085번 사탕 게임 (C++)

www.acmicpc.net/problem/3085

3085번: 사탕 게임

입력값이 최대 50이므로 완전 탐색으로 어렵지 않게 해결할 수 있는 문제입니다. 가로와 세로 각각 인접한 사탕이 다른 경우 자리를 교체해가면서, 전체 영역의 가로 세로를 탐색하면 됩니다. 다만 eat() 함수 부분에서 한 줄이 모두 같은 경우 최대값 갱신 처리를 따로 처리해줘야 하는 것을 조심해야합니다. 

 

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

vector<string> map(53);
int n, answer;

void eat() {
    // 가로 사탕 먹기
    for(int i = 0; i < n; i++) {
    	int sum = 1;
        for(int j = 0; j < n - 1; j++) {
            if(map[i][j] == map[i][j + 1]) {
                sum++;
            } else {
                answer = max(answer, sum);
                sum = 1;
            }
    	}
    	// 한 줄이 모두 같은 경우 최대값 갱신이 안되므로 따로 처리  
    	answer = max(answer, sum);
    }
    
    // 세로 사탕 먹기
    for(int i = 0; i < n; i++) {
    	int sum = 1;
        for(int j = 0; j < n - 1; j++) {
            if(map[j][i] == map[j + 1][i]) {
                sum++;
            } else {
                answer = max(answer, sum);
                sum = 1;
            }
    	}
    	// 한 줄이 모두 같은 경우 최대값 갱신이 안되므로 따로 처리
    	answer = max(answer, sum);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(int i = 0; i < n; i++) {
        cin>>map[i];
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n - 1; j++) {
            // 가로 사탕 교환
            if(map[i][j] != map[i][j + 1]) {
                swap(map[i][j], map[i][j + 1]);
                eat();
                swap(map[i][j], map[i][j + 1]);
            }
            
            // 세로 사탕 교환
            if(map[j][i] != map[j + 1][i]) {
                swap(map[j][i], map[j + 1][i]);
                eat();
                swap(map[j][i], map[j + 1][i]);
            }
        }
    }
    
    cout<<answer;
}