행렬

1080번: 행렬

 

나의 풀이

import sys

def _change_3X3(change_map, s_a, s_b): # 변환 함수 (3X3)
    for i in range(s_a, s_a + 3):
        for j in range(s_b, s_b + 3):
            change_map[i][j] = 1 - change_map[i][j]
    return change_map

def _sq_array(a, b, change_map, now_map):
    answer = 0
    for i in range(a - 2): # 변환할 (3x3 배열 찾기)
        for j in range(b - 2):
            if change_map[i][j] != now_map[i][j]:
                answer += 1
                change_map = _change_3X3(change_map, i, j) # 변환
    if (change_map == now_map):
        return answer
    else:
        return -1

a, b = map(int, sys.stdin.readline().rstrip().split())
change_map, now_map = [], []
for i in range(2):
    for _ in range(a):
        if (i == 0):
            change_map.append(list(map(int, sys.stdin.readline().rstrip())))
        else:
            now_map.append(list(map(int, sys.stdin.readline().rstrip())))
print(_sq_array(a, b, change_map, now_map))

 

시간 복잡도

for i in range(a - 2) : 변환할 배열 찾기 ( 이차형 시간 복잡도 )
    for j in range(b - 2) :
        3x3 내부 변환 루프 ( 상수 시간 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n**2) )