[PS] BOJ1080 행렬 ( greedy ) With 파이썬

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

1080번: 행렬

 

◎문제풀이 

 

아직 그리디 문제풀이의 감이 부족한것 같다. 

 

최솟값을 구하는 문제라 두 행렬의 차이가 가장 많이 나는 좌표를 추출하여 3X3행렬을 뒤집는 방법으로 풀이를 시도했다. 그런데 이 문제는 그냥 좌표를 차례대로 확인하면서 틀린부분이 있으면 3x3행렬을 뒤집으면 되었다. 현재를 기준으로 최적해를 구하는 것이 그리디 문제이다. 전체에서 가장 많이 차이나는 좌표를 구하여 문제를 푸는 것이 아니다.

 

 

◎코드

#BOJ1080 행렬 ( greedy )
n,m = map(int,input().split())

mx1 = [[0] for _ in range(n)] #행렬1
mx2 = [[0] for _ in range(n)] #행렬2

for i in range(n) :
  mx1[i] = list(map(int,input().rstrip("\n")))
for i in range(n) :
  mx2[i] = list(map(int,input().rstrip("\n")))

#3X3 좌표이동 리스트
dx = [0,1,2,0,1,2,0,1,2] 
dy = [0,0,0,1,1,1,2,2,2]

# 행렬 뒤집는 함수
def reverse_mx(x,y) :
  for i in range(9) :
    nx = x+dx[i]
    ny = y+dy[i] 
    mx1[ny][nx] = 1 - mx1[ny][nx] 

#두 행렬 일치여부 확인 함수
def issame() :
  for i in range(n) :
    for j in range(m) :
      if mx1[i][j] != mx2[i][j] : return False
  return True
  
#풀이
ans = 0
for i in range(n-2) : 
  for j in range(m-2) :
    if mx1[i][j] != mx2[i][j] :
      reverse_mx(j,i)
      ans += 1

#출력
if issame() : print(ans)
else : print(-1)