백준 15925번 욱제는 정치쟁이야!! [C++]

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

 

 

#문제 간단 정리

구현 + 브루트 포스 문제

 

#문제 해결 방법

우선 브루트포스로 문제를 풀리게하도록 고심한 흔적이 여럿 보이는데 

 

문제의 n 이 31 까지로 상당히 작고 

보드가 홀수로만 주어진다는 점이 주목할만한 점인데

 

만약 행이나 열을 1 이나 0으로 바꾸게 되면 

항상 1이나 0이 늘어나기 때문에 다음에 더 유리한 조건이 된다

 

때문에 행과 열을 반복해서 교차로 키거나 끌 수 있는지 확인해주면 (N^2)

 

한번 키거나 끌 때 N개의 컴퓨터가 바뀌니까  이 작업이 최대 N 번복

 

N^2 * N 해서 대략 N^3 정도인 듯 하다 

나머지는 개인의 구현 역량에 따라 구현하면 된다.

 

#전체 코드

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

int n;
int isUse;
vector<vector<int>> board;

bool checkRow() {

    bool check = false;

    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (board[i][j] == isUse) count++;
        }

        if (count > n / 2 && count != n) {
            for (int j = 0; j < n; j++) {
                board[i][j] = isUse;
            }
            check = true;
        }
    }

    return check;

}

bool checkCol() {

    bool check = false;

    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (board[j][i] == isUse) count++;
        }

        if (count > n / 2 && count !=n) {
            for (int j = 0; j < n; j++) {
                board[j][i] = isUse;
            }
            check = true;
        }
    }

    return check;
}

bool isConfirm() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] != isUse) return false;
        }
    }

    return true;
}

bool isPossible() {

    while (true) {

        if (!checkRow() && !checkCol()) {
            if (isConfirm()) {
                return true;
            }else    return false;
        
        }

  
    }


}

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

    cin >> n;
    cin >> isUse;

    board.resize(n, vector<int>(n));

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

    if (isPossible()) {
        cout << 1 << endl;
    }
    else cout << 0 << endl;


    return 0;
}