[백준] 1080번 행렬 - Python / 알고리즘 중급 1/3 - 그리디 알고리즘

---

---

---

💡 문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

---

💭 접근

이 문제의 목적은 "최소 횟수"로 A를 B로 바꾸는 것이다. 따라서 만약 A의 어떤 칸이 0인데 B에서의 그 칸이 1이라면 반드시 뒤집어야한다.
또한, 연산의 특성 상, 2번 이상 뒤집는 것은 결국 똑같은 것으로 바꾸는 것이기 때문에 의미가 없다.

그러면 이 문제를 해결하기 위해선, A와 B가 다른 칸이 있다면 반드시 바꾸고 그 영역을 기준으로 3x3이 다르다고 해서 다시 뒤집지 않는다.(이미 확인한 칸은 다시 확인하지 않는다.)

모든 칸을 확인한 이후, A와 B가 같아졌다면 바꾼 횟수를 출력하고 다르다면 -1을 출력한다.

---

📒 코드

def toggle(x, y):
    for i in range(3):
        for j in range(3):
            if a[x + i][y + j] == 0:
                a[x + i][y + j] = 1
            else:
                a[x + i][y + j] = 0

n, m = map(int, input().split())
a = [list(map(int, input())) for _ in range(n)]
b = [list(map(int, input())) for _ in range(n)]

ans = 0
for i in range(n - 2):
    for j in range(m - 2):
        if a[i][j] != b[i][j]:
            ans += 1
            toggle(i, j)

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

---

💭 후기

문제의 특징과 요구사항을 파악해서 그리디 알고리즘을 사용할 수 있는가 판단을 내리는 연습을 많이 해야겠다.

---

🔗 문제 출처

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

---