[Algorithm] programmers-131703-2차원 동전 뒤집기.java

/* 
# 첫 번째 시도
dfs로 탐색? -> 시간초과 ㅠㅠ

# 두 번째 시도
1. 행의 모든 경우의 수를 구함. 
2. 이후 열을 탐색해보는데 3가지 경우가있따
    a. 열이 target과 모두 일치 -> 아무것도 안한다
    b. 열이 target과 정 반대 -> 뒤집어주고 count+1
    c. a도b도아니다 -> 정답이 아니니 료
*/
class Solution {
    static int[][] map; //global beginning 
    static int[][] tar; //glboal target
    static int min = Integer.MAX_VALUE;
    static int n; //행
    static int m; //열

    public int solution(int[][] beginning, int[][] target) {
        n = beginning.length;
        m = beginning[0].length;
        visitedRow = new boolean[n];
        visitedCol = new boolean[m];
        map = beginning;
        tar = target;
        dfs(0,0);
        return min==Integer.MAX_VALUE?-1:min;
    }

    static void dfs(int row, int count){
        if(row==n) {
            int result = count;
            for(int col=0 ; col<m ; col++){
                if(diffColCount(col) == n) result++;
                else if(diffColCount(col) != 0) return;
            }
            min = Math.min(min, result);
            return;
        }

        turnRow(row);
        dfs(row+1, count+1); //뒤집는 경우
        turnRow(row);
        dfs(row+1,count); // 뒤집지 않는 경우
    }
    /* 행 뒤집기 */
    static void turnRow(int row){
        for(int i=0;i<m;i++){
            map[row][i] = turn(map[row][i]);
        }
    }

    /* 뒤집기 */
    static int turn(int k){
        if(k==0) return 1;
        return 0;
    }

    /* 각 열마다 일치하는 개수 반환*/
    static int diffColCount(int col){
        int count = 0;
        for(int i=0;i<n;i++){
            if(map[i][col] != tar[i][col]) count++;
        }
        return count;
    }
}