백준15925 욱제는 정치쟁이야!!

작성일 | In

문제 링크

  • http://icpc.me/15925

문제 출처

  • 제2회 천하제일 코딩대회 J번

시간복잡도

  • O(n2)

풀이

이 문제는 모든 칸을 s로 만들 수 있는지를 확인하는 문제입니다.
만약 s가 0이라면 모든 컴퓨터의 상태를 반전시켜 s가 1인 문제로 바꾸어서 풀겠습니다.

N이 5라고 가정을 하고 설명을 하겠습니다.
어떤 행의 상태가 (1, 1, 0, 1, 0) 이라면, 모두 1로 바꿔주면 됩니다.
반대의 경우에는 이 행만 이용해서 1로 바꿀 방법이 없습니다. 하지만, 0들이 속한 열에서 1로 바꿀 방법이 있을 수는 있습니다.

그러므로 먼저 모든 행을 탐색해서 1로 만들 수 있다면 먼저 만들어줍시다.
그 다음에 모든 열을 탐색하면서 행을 탐색할 때 1로 만들지 못했던 값들을 1로 만들 수 있으면 만들어줍니다.
마지막으로 모든 행을 다시 한 번 탐색해서 1로 만들 수 있다면 1로 만들어줍니다.
행 - 열 - 행 순으로 탐색을 하면 행들의 값을 결정할 수 있습니다. 반대로, 열 - 행 - 열 순으로 탐색을 하면 열들의 값을 얻을 수 있겠죠.
행 - 열 - 행 - 열 순으로 탐색하면 답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

int n, s;
int arr[40][40];

void rev(){
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) arr[i][j] = !arr[i][j];
}

bool f(){
	bool flag = 1;
	int t;
	for(int i=0; i<n; i++){
		t = 0;
		for(int j=0; j<n; j++) if(arr[i][j]) t++;
		if(t > n/2) for(int j=0; j<n; j++) arr[i][j] = 1;

		t = 0;
		for(int j=0; j<n; j++) if(arr[j][i]) t++;
		if(t > n/2) for(int j=0; j<n; j++) arr[j][i] = 1;
	}

	for(int i=0; i<n; i++) for(int j=0; j<n; j++){
		if(!arr[i][j]) flag = 0;
	}

	return flag;
}

int main() {
	cin >> n >> s;
	for (int i=0; i<n; i++) for (int j=0; j<n; j++)	cin >> arr[i][j];
	if(!s) rev();

	bool value = f();
	value = f();

	if (value) printf("1");
	else printf("0");
}