[백준 1080번] 행렬 (java)

1080번: 행렬

 

A[r][c]에 대하여 A[r][c]!=B[r][c] 이면, (r, c)를 시작으로하는 3*3 행렬만큼 0은 1로, 1은 0으로 뒤집는다.

위 과정을 r = 0, c = 0 부터 마지막까지 반복한다.

 

이렇게 하는 이유는 만약에 A[0][0]!=B[0][0] 라면 B[0][0]와 같게 하기 위해 A[0][0]를 뒤집어야 한다.

그런데 A[0][0]를 뒤집기 위해서는 결국 (0,0)을 맨 왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다.

 

 

A[0][1]도 마찬가지이다. A[0][1] != B[0][1] 라면 B[0][1]와 같게 하기 위해서 A[0][1]를 뒤집어야 하는데,

이 때 (0,1)을 포함하는 3*3 행렬만큼 뒤집어주면 된다.

그런데 (0,0)은 이미 이 직전에 한 번 뒤집어서 변경해주었다. 뒤집은 자리를 한 번 더 뒤집어주면 불필요한 연산을 한 번 더 해주는 것이기 때문에 연산의 최소횟수를 구할 수 없게 된다.

그러므로 (0,0)을 포함시키지 않도록 (0,1)을 맨왼쪽위로 하는 3*3 행렬만큼을 뒤집어야 한다.

 

이런식으로 r = 0, c = 0 부터 시작해서 A[r][c]가 B[r][c]와 다르면 해당 위치를 맨 왼쪽위로 하는 3*3 행렬만큼의 요소를 뒤집어준다.

여기서 핵심은 3*3 행렬이 계속 이동하면서, 이미 뒤집은 요소(회색부분)는 다시는 뒤집지 않는다.

그렇기 때문에 연산을 최소로 하면서 행렬 A를 행렬 B와 일치시키도록 바꿔나갈 수 있다.

 

 

만약 반복이 끝났는데도 행렬 A와 행렬 B가 일치하지 않는다면 -1을 출력하고,

일치한다면 3*3만큼 뒤집은 횟수를 출력한다.

 

 

소스코드 :