[pro] 프로그래머스 level3 131703 2차원 동전 뒤집기 (Java) - DFS

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

 

[풀이]

할 수 있는 행동은 행을 뒤집거나, 열을 뒤집는 것 2가지이다. 

만약 모든 경우의 수를 따진다면, (n개의 행을 뒤집거나 뒤집지 않는 경우의 수) 2^n ×  2^m (m개의 열을 뒤집거나 뒤집지 않는 경우의 수) 이 될 것이다.

그러나, 모든 행을 뒤집거나 뒤집지 않는 경우를 구한 이후, 열에 대해서는 모든 경우를 다 살펴보지 않아도 되기 때문에 2^n 만으로 해결 가능하다.

위의 그림에서 모든 열에 대해 취할 수 있는 행동은 다음 3가지이다.

1) target과 똑같다면 뒤집지 않는다.

2) target과 정반대라면 뒤집는다.

3) 1, 2의 경우가 아니라면 target을 만들 수 없다.

 

[코드]

 

class Solution {
    int n, m;
    int[][] board;
    int[][] t;
    int ans = Integer.MAX_VALUE;
    public int solution(int[][] beginning, int[][] target) {
        int answer = 0;
        //초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 
        n = beginning.length;
        m = beginning[0].length;
        
        board = new int[n][m];
        for(int i=0; i<n; i++){
            board[i] = beginning[i].clone();
        }
        t = target;
        
        dfs(0, 0);
        
        if(ans==Integer.MAX_VALUE){
            answer = -1;
        } else answer = ans;
        
        return answer;
    }
    
    public void flip_row(int r){
        //0->1, 1->0
        for(int i=0; i<m; i++){
            board[r][i] = (board[r][i]+1)%2;
        }
    }
    
    public int compare_col(int c){
        int check = 0;
        for(int i=0; i<n; i++){
            if(t[i][c]==board[i][c]){
                check++; 
            } 
        }
        
        if(check==n) return 0; //전부 일치
        else if(check==0) return 1; //전부 불일치
        else return -1;
    }
    
    public void dfs(int r, int cnt){
        //모든 행의 경우의 수를 확인했다면
        if(r==n){
            boolean flag = true;
            for(int i=0; i<m; i++){
                int result = compare_col(i);
                if(result==-1){
                    flag = false;
                    break;
                }
                cnt += result; //전부 반대일 경우 +1
            }
            
            if(flag){
                ans = Math.min(ans, cnt);   
            }
            return;
        }
        
        flip_row(r); //행 뒤집기
        dfs(r+1, cnt+1); //행을 뒤집는 경우
        flip_row(r); //다시 원상태로
        
        dfs(r+1, cnt); //행을 뒤집지 않는 경우
    }
}