2차원 동전 뒤집기

2025-10-11

#JAVA#프로그래머스

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;
    }
}