[백준] 행렬 1080 (Python)

문제 링크

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

1080번: 행렬

나의 풀이

처음 잘못된 접근

• 문제에서 행렬을 변환하는 연산은 어떤 3 × 3 크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0) 이 부분을 읽지 못해 DFS로 접근하려는 생각을 했습니다.
• 위 조건 때문에 DFS로 접근하는 것은 잘못된 접근입니다.

Greedy를 이용한 접근

• 정말 간단하게 행렬을 탐색하며 비교하는 행렬과 다르면 해당 위치를 기준으로 3X3 만큼 뒤집어 주면 됩니다.
• 이때 index error방지를 위해 행렬을 탐색할 때 탐색 범위를 row, column 모두 -2만큼 빼주면서 진행합니다.

Code

row, col = map(int,input().split())

a = [list(map(int,input()))for _ in range(row)]
b = [list(map(int,input()))for _ in range(row)]

def convert(x,y):
    for i in range(3):
        for j in range(3):
            a[x+i][y+j] = 1 - a[x+i][y+j]

answer = 0

for i in range(row-2):
    for j in range(col-2):
        if a[i][j] != b[i][j]:
            convert(i,j)
            answer += 1
        if a == b:
            break
    if a==b:
        break

if a == b:
    print(answer)
else:
    print(-1)

Git

https://github.com/youngh0/Algorithm/blob/master/greedy/boj_1080_matrix.py