BOJ) 행렬

행렬

1080번: 행렬

풀이

 

n by m 으로 이루어진 두 행렬이 주어진다.

두 행렬이 같은지 비교하고, 만약 다르다면 3 by 3의 크기만큼 0->1, 1->0 으로 변환할 수 있다.

최소 몇 번을 값을 바꿔야 같아지는지 횟수를 구하는 문제다.

구할 수 없을 때는 -1을 출력한다.

 

Brute force 문제라고 생각해서 전체 탐색을 돌렸다.

특정 알고리즘이 들어가지 않고, 행렬을 비교하고, 다르다면 3 by 3의 행렬값을 뒤짚어주면서 답을 찾았다.

탐색이 끝난 이후에도 한번 더 행렬이 같은지 검사하여, 같다면 여태까지 값을 변경해온 count를, 다르다면 -1을 출력하도록 설정했다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private final static char ONE = '1', ZERO = '0';
    private final static int DIV = 3;
    private static int n,m;

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

        char[][] map = new char [n][m];
        char[][] target = new char[n][m];

        for(int i=0; i<n; i++) {
            map[i] = br.readLine().toCharArray();
        }
        for(int i=0; i<n; i++) {
            target[i] = br.readLine().toCharArray();
        }

        br.close();
        solution(map, target);
    }

    private static void solution(char[][] map, char[][] target) {
        int answer =0;
        boolean isSame = false;

        for(int y=0; y<=n-DIV; y++) { // 시작점 y
            for(int x=0; x<=m-DIV; x++) { // 시작점 x
                isSame = isSameMap(map,target);
                if(isSame) { break; }
                else {
                    if(map[y][x] != target[y][x]) { // 시작점이 다르면 바꿔야겠네?
                        map = getReverseMap(map, x, y);
                        answer++;
                    }
                }
            }
        }
        isSame =isSameMap(map,target);
        if (!isSame) { answer = -1; }
        System.out.println(answer);
    }

    private static boolean isSameMap(char[][] map, char[][] target) {
        for(int y=0; y<n; y++) {
            for(int x=0; x<m; x++) {
                if(map[y][x] != target[y][x]) { return false; }
            }
        }
        return true;
    }

    private static char[][] getReverseMap(char[][] map, int x, int y) {
        for(int findY= y; findY <y+DIV; findY++) {
            for(int findX =x; findX <x+DIV; findX++) {
                if(map[findY][findX] == ZERO) { map[findY][findX] = ONE; }
                else { map[findY][findX] = ZERO; }
            }
        }
        return map;
    }

    private static char[][] copyMap(char[][] map) {
        char[][] result = new char[n][m];
        for(int y=0; y<n; y++) {
            for(int x=0; x<m; x++) {
                result[y][x] = map[y][x];
            }
        }
        return result;
    }
}