[Algorithm] 정올 1037 오류교정

[ 문제 ]

패리티 검사법은 메시지를 주고받을 때 메시지가 패리티 성질을 가지고 있을 경우엔 메시지가 제대로 도착을 하였다 보고 그렇지 않을 경우 메시지가 제대로 도착을 하지 않았다고 판별을 하는 메시지 전송시의 오류 판별 및 교정을 하는 방법을 말한다.

 

불리언 행렬의 각각의 열과 각각의 행이 짝수 합을 가질 때 패리티 성질을 가지고 있다고 하자.

다시 말하자면 한 집합에 짝수개의 1이 있다는 이야기 이다.

 

아래는 패리티 성질을 가진 4 x 4의 행렬이다.

 

1 0 1 0

0 0 0 0 

1 1 1 1 

0 1 0 1

 

각각의 행의 합은 2, 0, 4, 2 이고 열의 합은 2, 2, 2, 2 이다.

 

당신이 할일은 행렬의 정보를 읽어서 이것이 패리티 성질을 가지고 있는지 없는지 판단해야한다. 만약 그렇지 않을 경우 하나의 비트를 바꿔서 이 행렬이 패리티 성질을 가질 수 있는가 확인하고 그렇지 않을 경우 행렬은 잘못된 행렬이라고 판단한다.​ 

 

[ 입력형식 ]

• 첫줄에는 행렬의 크기인 n(n<100) 이 입력되며 n개의 줄에 n개의 0혹은 1이 입력된다.

 

[ 출력형식 ]

• 만약 행렬이 패리티 성질을 가질 경우 "OK"라 출력하고 하나의 비트만을 변경해서 패리티 성질을 가질 경우 바꿔야 될 비트가 있는 i행 j열 에 대해 "Change bit (i,j)" 라 출력하며 두 경우에 해당되지 않을 때는 "Corrupt"라고 출력한다.
• * 주의 - 각각의 행과 열은 1부터 시작한다.

 

[ 입력 예 ]

4

1 0 1 0

0 0 0 0

1 1 1 1

0 1 0 1

 

[ 출력 예 ]

OK

 

---

 

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); // 행렬 크기
		int[][] matrix = new int[N][N];
			
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				matrix[i][j] = Integer.parseInt(st.nextToken());
		}
		
		int row = 0, column = 0; // 바꿔야 할 행 인덱스, 열 인덱스
		int rowCount = 0, columnCount = 0;			
		for (int i = 0; i < N; i++) {
			int rowSum = 0;
			int columnSum = 0;
			
			for (int j = 0; j < N; j++){
				rowSum += matrix[i][j];
				columnSum += matrix[j][i];
			}
            
			if (rowSum % 2 != 0) {
				row = i;
				rowCount++;
			}
				
			if(columnSum % 2 != 0) {
				column = i;
				columnCount++;
			}
		}
		
		if (rowCount == 0 && columnCount == 0)	System.out.println("OK");
		else if (rowCount == 1 && columnCount == 1)	System.out.println("Change bit (" + (row+1) + "," + (column+1) + ")");
		else	System.out.println("Corrupt");
	}

}