PGMS_2차원 동전 뒤집기 (Java)

[level 3] 2차원 동전 뒤집기 - 131703

문제 링크

성능 요약

메모리: 74 MB, 시간: 3.49 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2025년 09월 17일 11:28:01

문제 설명

한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.

예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.

직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.

---

제한사항

• 1 ≤ beginning의 길이 = target의 길이 ≤ 10
• 1 ≤ beginning[i]의 길이 = target[i]의 길이 ≤ 10
  • beginning[i][j]와 target[i][j]는 i + 1행 j + 1열의 동전의 상태를 나타내며, 0 또는 1의 값으로 주어집니다.
  • 0은 동전의 앞면을, 1은 동전의 뒷면을 의미합니다.

---

입출력 예

beginning	target	result
[[0, 1, 0, 0, 0], [1, 0, 1, 0, 1], [0, 1, 1, 1, 0], [1, 0, 1, 1, 0], [0, 1, 0, 1, 0]]	[[0, 0, 0, 1, 1], [0, 0, 0, 0, 1], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]	5
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]	[[1, 0, 1], [0, 0, 0], [0, 0, 0]]	-1

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 목표 상태를 만들지 못합니다. 따라서 -1을 return 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 풀이

처음에 보자마자 떠오른 방법은 dfs + 비트마스킹이지만 좀 더 수학적인 접근이 있을 것 같았다.

이후 생각한 방식으로 문제를 좀 더 단순화시킬 수 있었다.

먼저 처음과 끝 상태가 주어져있기 때문에 어떤 칸이 뒤집혔고, 뒤집히지 않았는지를 알 수 있다. 이를 XOR 연산으로 한번에 구할 수 있다.

즉 어떤칸이 짝수번 뒤집혔고 홀수번 뒤집혔는지를 알 수 있다는 의미다.

이후 정답 값에 관한 생각도 할 수 있었는데 (row + col) 값보다 커질 수 없었다. 왜냐하면 뒤집을 줄의 조합은 교환법칙이 성립하고 그걸 두번 뒤집으면 뒤집지 원상복구이기 때문에 뒤집지 않은것과 같은 효과기 때문이다.

따라서 모든 열 종류 + 모든 행 종류에서 뒤집거나 뒤집지 않거나 중 하나인 것이다.

따라서 나는 이 문제를 다음과 같이 바꾸었다.

=> “뒤집을 행 + 열의 조합을 결정하는 결정 문제”

이제 이를 쉽게 구하는 방법은 먼저 열 종류 중에서 뒤집을 조합을 정하고 (비트마스킹 조합), 이후 행들도 XOR에서 뒤집어야함을 1로 체크하면 그 행을 뒤집는다. 이후 완료되었는지를 보고 잘 완성되었으면 그 cnt를 최솟값갱신한다.

코드

import java.util.*;

class Solution {
    static int n, m, res;
    static int [][] XOR;
    static boolean isValidRes = false;
    public int solution(int[][] beginning, int[][] target) {
        res = Integer.MAX_VALUE;
        n = beginning.length;
        m = beginning[0].length;
        XOR = new int[n][m];
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                XOR[i][j] = beginning[i][j] ^ target[i][j];
            }
        }
        
        for(int comb=0; comb<(1<<m); comb++){
            check(comb);
        }
        
    
        return isValidRes ? res : -1;
    }
    
    private void check(int comb){
        int[][] makeZero = new int[n][m];
        for(int a=0; a<n; a++){
            makeZero[a] = Arrays.copyOf(XOR[a], m);
        }
            
        int cnt = 0;
            
        for(int j=0; j<m; j++){
            if(((1<<j) & comb) != 0){ // 뒤집기조건
                cnt++;
                for(int i=0; i<n; i++){
                    makeZero[i][j] = 1-makeZero[i][j];
                }
            }
        }
            
        for(int i=0; i<n; i++){
            if(makeZero[i][0] == 1){
                cnt++;
                for(int j=0; j<m; j++){
                    makeZero[i][j] = 1-makeZero[i][j];
                }
            }
        }
            
        boolean flag = true;
        outer : for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(makeZero[i][j] != 0) {
                    flag = false;
                    break outer;
                }
            }
        }
        
        if(flag) {
            res = Math.min(res, cnt);
            if(!isValidRes) isValidRes = true;
        }
    }
}