프로그래머스 2차원 동전 뒤집기 자바 풀이

문제 링크

문제 풀이 시간 : 1시간 30분

문제 요약

문제 풀이

이 문제를 보면서 꽤 오랜시간 풀이 방향성을 고민해보았다.

그러다가 든 생각이 초기 상태와 목표 상태의 차이를 구해보는 것이다.

즉, 각 위치의 동전이 서로 다른 경우를 1, 같은 경우를 0으로 표시하여 뒤집어야 하는 위치를 구분하였다.

예를 들어, 아래 그림과 같은 상황이 있다고 할 때,

초기 상태와 목표 상태를 XOR 연산과 같이 비교하면 뒤집어야 하는 위치를 1, 뒤집지 않아도 되는 위치를 0으로 표시할 수 있다.

이렇게 얻은 차이 행렬은 아래와 같다.

이제 목표는 이 차이 행렬을 전부 0으로 만드는 최소 뒤집기 횟수를 찾으면 되는 것이다!

이 문제에서는 행과 열을 한번씩 뒤집는 두가지 연산만 가능하기 때문에 각 행, 열을 뒤집을지 말지를 선택하는 완전탐색으로 접근했다.

행을 모두 탐색하고, 열을 탐색하는 방식으로 모든 조합을 탐색하면서 최종적으로 차이 행렬이 전부 0이 되는 경우의 최소 횟수를 구했다.

핵심 코드

모든 동전이 0인지 확인해주는 함수

java

public boolean check(){
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(diff[i][j]!=0)
                    return false;
            }
        }
        return true;
    }

aixs에 따라 한 행, 열을 모두 뒤집어 주는 함수

java

public void flip(int x, int axis){
        if(axis == 0){ //행 뒤집기
            for(int i=0;i<col;i++){
                diff[x][i] = diff[x][i] == 0 ? 1 : 0;
            }
        }
        else{ //열 뒤집기
            for(int i=0;i<row;i++){
                diff[i][x] = diff[i][x] == 0 ? 1 : 0;
            }
        }
    }

모든 조합을 백트래킹으로 탐색하며 최소 뒤집기 횟수 구하는 함수

java

public void calc(int r, int c, int sum){
        if(r==row){
            if(c==col){
                if(check())
                    ans = Math.min(ans, sum);
                return;    
            }
            
            calc(r, c+1, sum);
            
            flip(c,1);
            calc(r,c+1, sum+1);
            flip(c,1);
            
            return;
        }
        
        calc(r+1, c, sum);
            
        flip(r,0);
        calc(r+1,c,sum+1);
        flip(r,0);
    }

최종 코드

java

class Solution {
    public int ans = Integer.MAX_VALUE;
    public int col, row;
    public int[][] diff;
    
    public void calc(int r, int c, int sum){
        if(r==row){
            if(c==col){
                if(check())
                    ans = Math.min(ans, sum);
                return;    
            }
            
            calc(r, c+1, sum);
            
            flip(c,1);
            calc(r,c+1, sum+1);
            flip(c,1);
            
            return;
        }
        
        calc(r+1, c, sum);
            
        flip(r,0);
        calc(r+1,c,sum+1);
        flip(r,0);
    }
    
    public void flip(int x, int axis){
        if(axis == 0){
            for(int i=0;i<col;i++){
                diff[x][i] = diff[x][i] == 0 ? 1 : 0;
            }
        }
        else{
            for(int i=0;i<row;i++){
                diff[i][x] = diff[i][x] == 0 ? 1 : 0;
            }
        }
    }
    
    public boolean check(){
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(diff[i][j]!=0)
                    return false;
            }
        }
        return true;
    }
    
    public int solution(int[][] beginning, int[][] target) {
        int answer = 0;
        col = beginning[0].length;
        row = beginning.length;
        diff = new int[row][col];
        
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                diff[i][j] = beginning[i][j]==target[i][j] ? 0 : 1;
            }
        }
        
        calc(0,0,0);
        
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

2차원 동전 뒤집기

문제 풀이 시간 : 1시간 30분

문제 요약

문제 풀이

핵심 코드

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기