[BOJ] 1080. 행렬(Greedy, 탐욕 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값

- 행렬 변환 연산은 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

기준이 되는 좌표에 해당하는 행렬 A에서의 원소와 행렬 B에서의 원소가 같다면 pass하고,

다르다면 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집어주면 된다.

특정 구간에서 한 번 뒤집은 행렬을 다시 뒤집으면 원상태로 돌아오게 되므로

특정 구간에서 한 번 수행한 행동은 다시 하지 않는다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

N, M = map(int, input().split())   A = [list(map(int, input())) for _ in range(N)] B = [list(map(int, input())) for _ in range(N)]   def flip(x, y, A):     for i in range(3):         for j in range(3):             A[x+i][y+j] ^= 1   ans = 0 for i in range(N-2):     for j in range(M-2):         if A[i][j] != B[i][j]:             flip(i, j, A)             ans += 1   print(ans if A == B else -1)

cs

line 6) 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집어주는 함수

line 9) 비트 반전을 위해 XOR 연산 사용

line 12~13) 행렬 좌표를 탐색, 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집어줘야 하므로, N-2, M-2 까지 탐색

line 14) 행렬 A, B에서 특정 좌표에 해당하는 원소의 값이 다를 경우, 

해당 좌표를 기준으로 3*3 크기의 부분 행렬에 있는 모든 원소를 뒤집어준다.

그러고 횟수 cnt++