[Python] 백준 - 행렬 (1080)

문제 설명

📃 문제 링크

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

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

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

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

예제 입력 1

3 4
0000
0010
0000
1001
1011
1001

예제 출력 1

2

🎈 문제 풀이

현재 상황에서 가장 최선의 선택을 하는 그리디 알고리즘을 사용하는 문제이다.

A 행렬의 모든 리스트 요소를 돌면서 현재 요소가 B 행렬의 요소와 다르다면 현재 위치에서부터 3 3 크기를 모두 뒤집어 준다. 나는 3 3 을 뒤집는 코드를 따로 함수로 빼 주었다. 끝까지 한 뒤 A 행렬과 B 행렬이 같으면 answer를 출력하고, 같지 않다면 불가능한 것이기 때문에 -1을 출력해 준다.

📝 소스 코드