[BOJ] 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을 출력한다.

코드

• C++ 17

#include <iostream> #include <string>   using namespace std;   int Ans; int N, M; string A[50]; string B[50];   // 주어진 좌표를 중심삼아 3x3의 부분 행렬을 뒤집는다. void Toggle(int r, int c) {     for (int i = r - 1; i <= r + 1; ++i)     {         for (int j = c - 1; j <= c + 1; ++j)             A[i][j] = '0' + '1' - A[i][j];     } }   // A행렬과 B행렬이 같은지 검사한다. bool IsSame() {     for (int r = 0; r < N; ++r)     {         if (A[r] != B[r])             return false;     }       return true; }   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);          cin >> N >> M;     for (int r = 0; r < N; ++r)         cin >> A[r];     for (int r = 0; r < N; ++r)         cin >> B[r];       for (int r = 1; r < N - 1; ++r)     {         for (int c = 1; c < M - 1; ++c)         {             // 해당 좌표를 선택할 것인지 말건지가 중요한데             // 좌상단 원소는 지나가버리면 다시는 변경할 수 없으므로             // 좌상단 원소를 비교해 선택 여부를 결정한다.             if (A[r - 1][c - 1] != B[r - 1][c - 1])             {                 Toggle(r, c);                 ++Ans;             }         }     }       cout << (IsSame() ? Ans : -1); }

• C# 6.0

using System;   namespace ForAlgoCsharp {     class Program     {         static int N, M, Ans;         static char[,] A = new char[50, 50], B = new char[50, 50];           static void Main(string[] args)         {             string[] inputs = Console.ReadLine().Split();             N = Convert.ToInt32(inputs[0]);             M = Convert.ToInt32(inputs[1]);               Input(A);             Input(B);               for (int r = 1; r < N - 1; ++r)             {                 for (int c = 1; c < M - 1; ++c)                 {                     if (A[r - 1, c - 1] != B[r - 1, c - 1])                     {                         Toggle(r, c);                         ++Ans;                     }                 }             }               Console.Write($"{(IsSame() ? Ans : -1)}");         }           static void Toggle(int r, int c)         {             for (int rr = r - 1; rr <= r + 1; ++rr)             {                 for (int cc = c - 1; cc <= c + 1; ++cc)                     A[rr, cc] = (char) ('0' + '1' - A[rr, cc]);             }         }           static bool IsSame()         {             for (int r = 0; r < N; ++r)             {                 for (int c = 0; c < M; ++c)                 {                     if (A[r, c] != B[r, c])                         return false;                 }             }               return true;         }           static void Input(char[,] arr)         {             for (int r = 0; r < N; ++r)             {                 var tempArr = Console.ReadLine().ToCharArray();                 for (int c = 0; c < M; ++c)                     arr[r, c] = tempArr[c];             }         }     } }

• Python 3

N, M = map(int, input().split()) A = [ [ int(x) for x in input() ] for i in range(N) ] B = [ [ int(x) for x in input() ] for i in range(N) ]   def toggle(r, c):     for i in range(r, r + 3):         for j in range(c, c + 3):             A[i][j] = 1 - A[i][j]   cnt = 0 for r in range(0, N - 2):     for c in range(0, M - 2):         if A[r][c] != B[r][c]:             toggle(r, c)             cnt += 1        print(f'{cnt if A == B else -1}')

복기

특별히 느리지 않는 한은 파이썬 기본 내장 함수인 input()과 print()를 쓰는 것이 낫다. sys.stdin.readline()을 사용하니 개행 문자가 들어오거나 들어오지 않는 혼용된 상태의 입력 케이스의 경우 처리하기 난감한 문제가 있다.