[백준 1080] 행렬 - Python (그리디)

 

1080번: 행렬

 

 

<내 코드>

 

N, M = map(int, input().split())
A = [list(map(int, list(input()))) for _ in range(N)]
B = [list(map(int, list(input()))) for _ in range(N)]

cnt = 0

def check():
    for i in range(N):
        for j in range(M):
            if A[i][j] != B[i][j]:
                return False
    return True


def solve(x, y):
    for i in range(x, x+3):
        for j in range(y, y+3):
            A[i][j] = 1 - A[i][j]  # 뒤집기

# 3*3 행렬의 왼쪽 상단 지점을 기준으로 삼는다.
for i in range(0, N-2):  # 0 ~ N-3
    for j in range(0, M-2):  # 0 ~ M-3
        if A[i][j] != B[i][j]:
            cnt += 1
            solve(i, j)

if check():
    print(cnt)
else:
    print(-1)

 

1. 3x3매트릭스의 특성을 고려하면 x의 범위는 [0, N-2]이고 y의 범위는 [0, M-2]이다.

2. [i][j]를 하나씩 늘려가며, 뒤지기 연산을 호출한다.

3. 마지막에는 A행렬과 B행렬이 같은지를 확인하고 같다면 solve() 호출 횟수를, 다르다면 -1을 반환한다.

 

(0,0) (N-1,0), (0, M-1), (N-1,M-1)의 값을 결정할 수 있는 부분 행렬은 딱 1개밖에 존재하지 않는다.

왼쪽 위 부터 오른쪽으로 하나씩 비교해가면서 다음 줄로 넘어가며 비교한다. 즉 3 x 3 행렬의 왼쪽 상단 점을 기준으로 A와 B가 같은지 비교하며 뒤집어 나간다. 한 번 지나간 기준점은 더 이상 바뀔 일이 없게 되며 이후 비교에 영향을 주지 않는다.