[백준] 1080번 : 행렬 - C++ / JAVA

 

백준 1080 : 행렬

등급 : Silver I

1080번: 행렬 (acmicpc.net)

1080번: 행렬

사용 알고리즘 : Greedy

사용 자료구조 : Vector

그림의 4×4 행렬에서 (0, 0)의 위치와 (1, 1)의 위치를 기준으로 3×3 크기의 행렬을 선택 후 반전하였을 때,

그림의 결과와 같이 어느 곳을 먼저 반전을 하든 같은 결과가 나옴을 볼 수 있다.

즉, 행렬 반전 함수의 경우 교환 법칙이 성립한다.

 

이 점을 이용하여, 처음부터 탐색 해 원하는 행렬과 값이 다른 정점이 나오는 경우 반전시키도록 하여 구현.

이때의 최솟값이 전체의 최솟값이 된다.

---

  1. 두 행렬의 크기와 값을 입력받는다.

  2. 3×3 행렬 반전 함수를 구현.

      ( 0과 1의 전환이므로, 현재 값에 1을 더하고 %2를 해주면 된다. )

  3. 코너 케이스 검사.

      1) 행렬이 3×3보다 작고, target과 값이 다른 경우 : 무조건 같아질 수 없으므로 -1.

      2) 행렬이 3×3보다 작지만, target과 값이 다른 경우 : 연산이 필요하지 않으므로 0.

  4. 이후, 행렬의 크기보다 2를 감소시킨 크기의 위치에서 서로 다른 값을 검사.

      ( 정점을 기준으로 옆으로 2칸씩 더 검사하는 것이므로, 넘어가는 곳은 볼 필요가 없기 때문 )

---

<hide/>
#include <iostream>
#include <vector>

using namespace std;

vector <vector <int>> v;
vector <vector <int>> target;

void input(vector <vector <int>> &v, int n, int m)
{
    string x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        for (int j = 0; j < m; j++)
        {
            v[i][j] = x[j] - '0';
        }
    }
}

void change(vector <vector <int>> &v, int x, int y)
{
    for (int i = x; i < x + 3; i++)
    {
        for (int j = y; j < y + 3; j++)
        {
            v[i][j] = (v[i][j] + 1) % 2;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    int ans = 0;
    cin >> n >> m;
    v.resize(n, vector <int>(m));
    target.resize(n, vector <int>(m));

    input(v, n, m);
    input(target, n, m);
    if (v == target)
    {
        cout << 0;
        return 0;
    }
    else
    {
        if (n < 3 || m < 3)
        {
            cout << -1;
            return 0;
        }
    }

    for (int i = 0; i < n - 2; i++)
    {
        for (int j = 0; j < m - 2; j++)
        {
            if (v[i][j] != target[i][j])
            {
                change(v, i, j);
                ans++;
            }
        }
    }
    if (v != target) cout << -1;
    else cout << ans;
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {

    static int n, m;
    static int[][] v, target;
    static void change(int x, int y)
    {
        for(int i=x; i<x+3; i++)
        {
            for(int j=y; j<y+3; j++)
            {
                v[i][j] = (v[i][j] + 1)%2;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int ans = 0;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = new int[n][m];
        target = new int[n][m];

        for(int i=0; i<n; i++)
        {
            String x = br.readLine();
            for(int j=0; j<m; j++)
            {
                v[i][j] = x.charAt(j) - '0';
            }
        }
        for(int i=0; i<n; i++)
        {
            String x = br.readLine();
            for(int j=0; j<m; j++)
            {
                target[i][j] = x.charAt(j) - '0';
            }
        }
        if(Arrays.deepEquals(v, target))
        {
            System.out.println(0);
            return;
        }
        else
        {
            if(n < 3 || m < 3)
            {
                System.out.println(-1);
                return;
            }
        }

        for(int i=0; i<n-2; i++)
        {
            for(int j=0; j<m-2; j++)
            {
                if(v[i][j] != target[i][j])
                {
                    change(i, j);
                    ans++;
                }
            }
        }

        if(Arrays.deepEquals(v, target)) System.out.println(ans);
        else System.out.println(-1);
    }
}