점괘 조작하기 (Fortune Fabrication)

문제

인덱스국 전쟁사 : Day 2

국왕 (검열됨)의 계속된 실정으로 찬란했던 인덱스국의 위용은 날로 쇠퇴해 갔고, 결국 이웃 나라 펜윅국이 인덱스국을 멸망시킬 준비를 하고 있다는 첩보가 입수되었습니다. (검열됨)은 왕실 역술가인 이멘을 불러 점을 치게 했습니다. 점괘가 '길'이 나오면 전쟁을, '흉'이 나오면 화친을 도모하려고 하는 것입니다.

인덱스국에서 점을 치는 데는 총 M행 N열로 나열된 뒤집히지 않은 동전 MN개가 사용됩니다. 점쟁이가 동전이 놓인 판을 크게 내리치면 몇 개의 동전이 뒤집히는데, 국왕이 보는 아래에서 그 점괘를 해석하여 전달합니다.

애석하게도 왕실 역술가 이멘조차 펜윅국의 첩자입니다. 그는 인덱스국의 군사력이 펜윅국을 당해낼 수 없음을 잘 알기 때문에, 점괘가 '길'이 되도록 조작하여 (검열됨)이 전쟁을 일으키도록 유도하려고 합니다.

이멘은 특수한 장치를 이용하여 판의 상태를 조작할 수 있는데, 한 번의 '조작'에서는 특정한 행, 열의 집합을 선택합니다. 이 때 어떤 동전의 행, 열이 모두 선택된 행, 열인 경우 그 동전을 뒤집습니다.

기계 장치를 너무 많이 사용하면 (검열됨)의 의심을 살 수 있기에 이멘은 '조작'의 횟수를 최소화하려고 합니다. 가능한 최소의 조작 횟수와 조작하는 방법을 하나 출력하는 프로그램을 작성해주세요.

구현 세부 사항

다음 함수를 구현하세요.

int[][] fabricate(int[][] G)

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.

• G는 '길' 점괘의 모양을 나타내는 M × N 의 2차원 배열입니다. '길' 점괘의 i + 1행 j + 1열에 해당되는 동전이 뒤집혀 있을 경우 G[i][j] = 1, 그렇지 않을 경우 G[i][j] = 0입니다.

• 이 함수는 필요한 조작 횟수를 F 라고 할 때, R[i]가 i + 1번째 조작에서 뒤집어야 할 열과 행의 정보를 나타내는 크기 F의 배열 R을 반환해야 합니다.

• 배열 R[i]는 i + 1번째 조작에 대한 정보를 담고 있습니다. (0 ≤ i ≤ F − 1)

• R[i]는 a번째 행을 뒤집어야 할 경우 a를 포함하고, b번째 열을 뒤집어야 할 경우 −b를 포 함해야 합니다. R[i] 내부에 중복 원소가 존재해서는 안되며, R[i]의 크기는 0 이상 N + M 이하여야 합니다.

제한 조건

• 2 ≤ M, N ≤ 2,000
• G[i][j] = 0, 1 (0 ≤ i ≤ M − 1, 0 ≤ j ≤ N − 1)

서브태스크

서브태스크	점수	M, N
1	2	M, N ≤ 3
2	10	M, N ≤ 500
3	8	M, N ≤ 2,000

모든 서브태스크에 대해서, 최소한의 조작 횟수만 맞힐 경우 서브태스크 점수의 40%를 얻을 수 있습니다.

예제 입출력

M = 2, N = 3, G = [[1, 1, 0], [1, 0, 1]]

그레이더는 다음의 함수를 호출합니다.

fabricate([[1, 1, 0], [1, 0, 1]])

fabricate가 반환할 수 있는 답의 예시는 다음과 같습니다.

R = [[1, −1, −2], [2, −1, −3]]

샘플 그레이더

샘플 그레이더는 다음의 형식으로 입력을 받습니다.

• Line 1 : M N
• Line 2 + i (0 ≤ i ≤ M − 1) : G[i][0] G[i][1] ··· G[i][N − 1]