백준 3085 - 사탕 게임

백준 algorithm

백준 3085 - 사탕 게임

cosmohoo 2020. 5. 31. 23:50

-> 오랜만에 푸는 알고리즘 문제입니다.

-> 그동안 스프링 공부하느라 포스팅을 못했습니다.......

=> 브루트 포스를 통해 풀어야 하는 문제입니다.

=> BFS DFS로 접근을 하려했지만 도저히 생각이 안 납니다.

배열의 오른쪽과 바꾸는 것과 배열의 아래쪽과 바꾸는 것 두 가지의 경우를 생각해야 합니다.
바꾼 다음에 check라는 함수를 만들어 위아래로 했을 때 길게 나오는 배열의 수와 옆으로 했을 때 길게 나오는 배열의 수를 확인해야 합니다.
위의 두 가지의 경우를 확인하고 각자 나온 결과값 중 가장 긴 값을 출력합니다.
배열의 길이보다 긴 최댓값은 없으므로, 배열의 길이만큼의 값이 나온다면 도중에 멈출 수 있습니다.

//
//  main.cpp
//  Baekjoon
//
//  Created by 이준후
//  Copyright © 2020 이준후. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int check(string Candy[], int size)
{
    int ans = 1;
    for(int i=0; i<size; i++)
    {
        int tmp = 1;
        for(int j=1; j<size; j++) //오른쪽으로 가는 경우
        {
            if( Candy[i][j] == Candy[i][j-1]) // 연속된다면
            {
                tmp++;
            }
            else
            {
                tmp =1;
            }
            if(ans < tmp) ans = tmp;
        }
        tmp = 1;//다시 셀거므로 reset
        for(int j=1; j<size; j++) //오른쪽으로 가는 경우
        {
            if( Candy[j][i] == Candy[j-1][i]) // 연속된다면
            {
                tmp++;
            }
            else
            {
                tmp =1;
            }
            if(ans < tmp) ans = tmp;
        }
    }
    return ans;
}

int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N;
    
    string Candy[50];
    
    int high=0;
    
    for(int i=0; i<N; i++)
    {
        cin >> Candy[i];
    }
    
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if((j+1) <N) // 오른쪽 부분과 바꾸는 경우
            {
                swap(Candy[i][j],Candy[i][j+1]);
                int tmp = check(Candy, N);
                high = max(high, tmp);
                swap(Candy[i][j],Candy[i][j+1]); //원상복구
            }
            
            if( (i+1) < N)
            {
                swap(Candy[i][j],Candy[i+1][j]);
                int tmp = check(Candy, N);
                high = max(high, tmp);
                swap(Candy[i][j],Candy[i+1][j]);
            }
        }
        if( high == N) break;
    }
    
    
    cout << high <<'\n';
    return 0;
}