[실버 1] 1080번: 행렬

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

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번 이상 연산을 적용해야 한다.
• 즉, 원소가 0이냐 1이냐 여부가 중요한 것이 아니라, 행렬 A의 원소가 행렬 B의 원소가 동일한지 여부가 중요한 것이다.
• 그러기 위해서는 행렬 C를 만들어서 행렬 A와 B의 원소가 동일하면 'O', 동일하지 않으면 'X'을 표시해주면 풀이를 찾는 데 도움이 될 것 같은데, 이 과정을 List Comprehension을 사용해서 구현하려면 너무 복잡하다. 그냥 C 스타일로 이중 반복문을 돌려야겠다.
• 만약 주어진 Input에 3×3 크기의 차이만 있다면, 부분 행렬을 한 번 뒤집는 것만으로 차이를 수정할 수 있다. 문제는 두 행렬의 차이의 크기가 정확히 3×3으로 떨어지지 않아서 여러 번 행렬을 뒤집어야 할 때이다.
• 어느 위치에서 행렬을 뒤집어야 할지 결정하기가 너무 까다롭다...
• 행렬을 '뒤집는다'는 개념으로 문제에 접근하면 답이 안 나온다. 좀 더 쉬운 개념으로 문제를 바꾸어 설명하면 문제가 해결되지 않을까?포기

남이 작성한 소스코드

푸르고 님:
https://puleugo.tistory.com/39
ImjDev 님:
https://mizzo-dev.tistory.com/41

피드백

• List Comprehension은 분명 Python의 강력한 도구이지만, 경우에 따라서 C 스타일의 이중 반복문보다 List Comprehension이 사용하기에 더 복잡할 수 있다.
• 한 칸씩 이동하면서 두 행렬의 해당 자리의 원소가 서로 일치하지 않으면 뒤집어 준다 → 곧바로 최소 연산 횟수를 도출할 수 있다.
• 더 이상 뒤집을 수 없을 때 두 행렬이 서로 다르면 두 행렬을 동일하게 만들 수 없으므로 -1을 출력해주면 된다.