[JAVA] 2차원 동전 뒤집기

 

2차원 동전 뒤집기

링크

프로그래머스

 

난이도 : Level 3

유형 : 그리디, 비트마스크

코딩테스트 연습 > 모든 문제 > 2차원 동전 뒤집기

문제 설명

한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다.
모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다.
동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.
예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다.
그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다.
초기 상태에서 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은 동전의 뒷면을 의미합니다.

 

풀이

초기 상태와 목표 상태를 나타내는 2차원 배열이 주어지고 초기 상태의 행과 열을 몇 번 뒤집어서 목표 상태와 같게 만들 수 있는지 찾는 문제이다.

가로와 세로의 뒤집는 순서는 뭐가 먼저든 상관없다.

그러니까 일단 행, 열 중 하나를 선택해서 모든 뒤집는 경우의 수를 만든다.

나는 첫 열을 기준으로 모든 행을 뒤집는 경우의 수를 만들고 각 경우의 수마다 첫번째 행을 기준으로 열을 뒤집어봐서 목표상태와 맞는 경우를 찾았다. 만약 모든 경우의 수를 다 봤는데도 일치하는 케이스가 없으면 목표상태로 갈 수 없는 것이다. 

배열 길이가 크지 않아서 완전탐색을 해도 문제가 없는 케이스였다.

 

그리고 모든 행을 뒤집는 경우의 수는 2^n 가지 이다. (n = 행의 길이)

왜냐면 하나의 요소에 0과 1만 가능하기때문이다. 

 

그래서 비트마스크를 만들어서 어떤 행을 뒤집을지 정했다. 

예를 들어, rowMask = 5 (이진수로 0101) 인 경우

• 0번째 행: 뒤집지 않음 
• 1번째 행: 뒤집음
• 2번째 행: 뒤집지 않음
• 3번째 행: 뒤집음

이런식으로

 

 

코드

 

class Solution {
    public int solution(int[][] beginning, int[][] target) {
        int rows = beginning.length; // 행의 수
        int cols = beginning[0].length; // 열의 수

        int minFlips = Integer.MAX_VALUE;

        // 모든 행 뒤집기 조합을 시도 (비트마스크 사용)
        for (int rowMask = 0; rowMask < (1 << rows); rowMask++) {
            int[][] current = copyArray(beginning); // 초기 상태 복사
            int flipCount = 0;

            // 행 뒤집기
            for (int r = 0; r < rows; r++) {
                if ((rowMask & (1 << r)) != 0) { // r번째 행을 뒤집음
                    flipRow(current, r);
                    flipCount++;
                }
            }

            // 열 뒤집기
            for (int c = 0; c < cols; c++) {
                if (current[0][c] != target[0][c]) { // 첫 번째 행을 기준으로 열 뒤집기 결정
                    flipColumn(current, c);
                    flipCount++;
                }
            }

            // 목표 상태와 일치하는지 확인
            if (isEqual(current, target)) {
                minFlips = Math.min(minFlips, flipCount);
            }
        }

        return (minFlips == Integer.MAX_VALUE) ? -1 : minFlips;
    }

    // 2차원 배열 복사
    private int[][] copyArray(int[][] array) {
        int[][] copy = new int[array.length][array[0].length];
        for (int i = 0; i < array.length; i++) {
            System.arraycopy(array[i], 0, copy[i], 0, array[i].length);
        }
        return copy;
    }

    // 행 뒤집기
    private void flipRow(int[][] array, int row) {
        for (int c = 0; c < array[0].length; c++) {
            array[row][c] = 1 - array[row][c];
        }
    }

    // 열 뒤집기
    private void flipColumn(int[][] array, int col) {
        for (int r = 0; r < array.length; r++) {
            array[r][col] = 1 - array[r][col];
        }
    }

    // 두 배열이 동일한지 확인
    private boolean isEqual(int[][] a, int[][] b) {
        for (int r = 0; r < a.length; r++) {
            for (int c = 0; c < a[0].length; c++) {
                if (a[r][c] != b[r][c]) {
                    return false;
                }
            }
        }
        return true;
    }
}