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

15925번: 욱제는 정치쟁이야!!

 

문제

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

15925번: 욱제는 정치쟁이야!!

---

풀이

브루트포스 문제로 O(N^2)으로 해결가능합니다. 사용 여부를 x라고 할 때, 한 행 또는 열에서 x가 N/2개 이상이면 모두 x로 바꿉니다.

 

문제의 예제 입력 1을 예로 들어 설명해보겠습니다.

5 0
0 0 0 1 1
1 1 0 1 1
0 1 0 0 0
0 1 1 1 0
1 0 1 1 1

일 때, 행부터 먼저 모두 살펴보면 1행, 3행은 모두 0으로 바뀝니다.

0 0 0 0 0
1 1 0 1 1
0 0 0 0 0
0 1 1 1 0
1 0 1 1 1

이제 열을 한 번 살펴봅시다. 1열, 2열, 3열, 5열이 모두 0으로 바뀝니다.

0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0

다시 한 번 행을 살펴보면 2행, 4행, 5행이 모두 0으로 바뀝니다. 그리고 모든 원소가 의도한대로 0이 되었으므로 1을 출력합니다.

 

요약해보면, 모든 행을 살펴봤을 때 바꿀 수 있는 행들은 모두 먼저 바꿔줍니다.

그 다음에 모든 열을 살펴보며 바꿀 수 있는 열들을 모두 바꿔줍니다.

이제 다시 한 번 모든 행을 살피면, 스스로 바뀔 수 없었던 행들이 바뀐 열들로 인해 바뀔 수 있게 됩니다.

즉, 행-열-행 순으로 살펴보면 행의 값을 결정할 수 있습니다. 반대로 열-행-열 순으로 살펴보면 열의 값을 결정할 수 있습니다.

따라서 행-열-행-열 순으로 살펴보면 답을 구할 수 있습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, x;
  cin >> n >> x;
  int arr[32][32];
  // 행렬 입력
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      cin >> arr[i][j];
  // 2번
  for (int k = 0; k < 2; k++)
    for (int i = 1; i <= n; i++) {
      // 행 탐색
      int cnt = 0;
      for (int j = 1; j <= n; j++)
        if (arr[i][j] == x)
          cnt++;
      if (cnt > n / 2)
        for (int j = 1; j <= n; j++)
          arr[i][j] = x;
      // 열 탐색
      cnt = 0;
      for (int j = 1; j <= n; j++)
        if (arr[j][i] == x)
          cnt++;
      if (cnt > n / 2)
        for (int j = 1; j <= n; j++)
          arr[j][i] = x;
    }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      // 하나라도 의도한대로 바꾸지 못한 경우
      if (arr[i][j] != x) {
        cout << 0;
        return 0;
      }
  // 이외의 경우
  cout << 1;
  return 0;
}