[PS 백준 - 2.4] 3085번: 사탕 게임

문제 정보

백준 3085번 - 바로가기

• 난이도: 실버 4
• 알고리즘: 브루트포스 알고리즘

---

코멘트

사탕이 인접한 경우 위치를 바꾸고 먹을 수 있는 개수의 최댓값을 검색한다. 이 때 위치를 바꾸는 것도 가로 / 세로 방향 두 가지 경우가 있고, 먹을 수 있는 개수를 탐색할 때도 가로 / 세로 방향 두 가지 경우가 존재한다. 따라서 총 4가지 경우의 수를 모두 빠짐없이 돌려줘야 한다.

---

소스 코드

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

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    
    int n;
    cin >> n;

    char** arr = new char*[n];
    
    for (int i = 0; i < n; i++) {
        arr[i] = new char[n];
    }
    string str;

    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < n; j++) {
            arr[i][j] = str[j];
        }
    }
    int max = 0;
    int count = 1;

    // 사탕 인접하면 바꾸고 먹을 수 있는 개수 검색하기
    // 가로 방향 바꾸기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {
            if (arr[i][j] != arr[i][j + 1]) {
                char temp = arr[i][j + 1];
                arr[i][j + 1] = arr[i][j];
                arr[i][j] = temp;

                // 바꾼 후 먹을 수 있는 개수 검색
                // 가로부터 검색
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < n-1; b++) {
                        if (arr[a][b] == arr[a][b + 1]) {
                            count++;
                        }
                        else {
                            max = max > count ? max : count;
                            count = 1;
                        }
                    }
                    count = 1;
                }

                // 세로 검색
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < n - 1; b++) {
                        if (arr[b][a] == arr[b+1][a]) {
                            count++;
                        }
                        else {
                            max = max > count ? max : count;
                            count = 1;
                        }
                    }
                    count = 1;
                }

                // 원상복구
                temp = arr[i][j + 1];
                arr[i][j + 1] = arr[i][j];
                arr[i][j] = temp;
            }
        }
    }

    //세로 방향 바꾸기
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n - 1; i++) {
            if (arr[i][j] != arr[i+1][j]) {
                char temp = arr[i + 1][j];
                arr[i + 1][j] = arr[i][j];
                arr[i][j] = temp;
                
                // 바꾼 후 먹을 수 있는 개수 검색
                // 가로부터 검색
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < n - 1; b++) {
                        if (arr[a][b] == arr[a][b + 1]) {
                            count++;
                        }
                        else {
                            max = max > count ? max : count;
                            count = 1;
                        }
                    }
                    max = max > count ? max : count;
                    count = 1;
                }

                // 세로 검색
                for (int a = 0; a < n; a++) {
                    for (int b = 0; b < n - 1; b++) {
                        if (arr[b][a] == arr[b + 1][a]) {
                            count++;
                        }
                        else {
                            max = max > count ? max : count;
                            count = 1;
                        }
                    }
                    max = max > count ? max : count;
                    count = 1;
                }

                // 원상복구
                temp = arr[i + 1][j];
                arr[i + 1][j] = arr[i][j];
                arr[i][j] = temp;
            }
        }
    }

    cout << max;

    for (int i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete arr;

}