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

문제 링크

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

사용 여부가 1이든 0이든 풀이는 같으니 0이라고 가정하고, N크기가 어떻든 풀이는 같으니 N = 5라고 가정하자.

N*N 정사각형에서 한 행을 보자.

이런 경우는 전부 0으로 만들 수 있으므로 한행을 전부 0으로 만든다.

이런 경우 행의 차원에서는 1을 0으로 바꿀 방법이 없다.

그럼 저 1은 누가 0으로 바꿀 수 있을까? 바로 해당 칸의 열에서 바꿀 수 있다. 

마찬가지로 한 열을 봤을 때

  

이런 경우에 저 1들은 해당 칸의 행에서만 0으로 바꿀 수 있다.

행 차원에서 모든 행을 먼저 탐색하고, 그 후 모든 열을 탐색하면 행의 차원에서만 봤을 때 바꾸지 못했던 1들의 값이 결정될테고, 다시 행을 훑어보면서 한 행을 0으로 바꿀지 말지 결정할 수 있다.

행 - 열 - 행 의 순서로 보면 행의 값들을 결정할 수 있으니 반대로 열 - 행 - 열의 순서로 탐색하면 열의 값들을 결정할 수 있다. 

따라서 행 - 열 - 행 - 열 의 순서로 탐색하면 모든 칸에 대해 값을 결정할 수 있다.

물론 열 - 행 - 열 - 행의 순서로 봐도 같은 답을 구할 수 있다.

정답 코드

	#include <iostream>
	using namespace std;
	int n, p[40][40], m;
	void foo() {
	for (int i = 0; i < n; i++) {
	int mcnt = 0;
	for (int j = 0; j < n; j++) {
	if (p[i][j] == m) mcnt++;
	}
	if (mcnt > n / 2) {
	for (int j = 0; j < n; j++) {
	p[i][j] = m;
	}
	}
	}
	for (int j = 0; j < n; j++) {
	int mcnt = 0;
	for (int i = 0; i < n; i++) {
	if (p[i][j] == m) mcnt++;
	}
	if (mcnt > n / 2) {
	for (int i = 0; i < n; i++) {
	p[i][j] = m;
	}
	}
	}
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	cin >> p[i][j];
	}
	}
	foo();
	foo();
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (p[i][j] != m) {
	cout << 0;
	return 0;
	}
	}
	}
	cout << 1;
	}

view raw 15925.cpp hosted with ❤ by GitHub

질문, 피드백 환영합니다.