[프로그래머스] Lv3 - 2차원 동전 뒤집기

문제 풀이 방법

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

 

문제에서 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하라고 합니다.

동전 뒤집기 횟수의 최솟값을 구하기 위해서 어떻게 해야할까요?

 

완전 탐색을 사용하는 경우의 시간 복잡도를 알아보겠습니다.

행과 열의 최대 범위는 둘다 10이 됩니다.

 

완전 탐색을 하는 경우, 각 행을 뒤집는 모든 경우 x 각 열을 뒤집는 모든 경우를 탐색하게 됩니다.

이는 O(2^(n+m))로 2^20이 됩니다.

 

모든 경우를 탐색하면서, target 배열과 비교해서 일치하는지 확인을 해야 합니다.

따라서, 최종 시간 복잡도는 O(2^(n+m) * n * m)이 됩니다.

 

최악의 경우 2^20 * 10 * 10이 되고, 이는 104,857,600이 되고, 시간복잡도가 1억이 넘어갑니다.

1억이 넘기 때문에 시간 복잡도를 줄여야 합니다.

 

어떻게 시간 복잡도를 줄일 수 있을까요?

 

행을 뒤집을 수 있는 모든 경우를 구하고, 행을 뒤집습니다. 그런 다음에 행을 뒤집은 보드판과 목표로 만들고자 하는 보드판의 모든 열을 비교합니다. 행을 뒤집은 보드판과 목표로 만들고자하는 보드판의 열의 모양을 비교해서 완전히 반대 모양이 되는 경우를 찾습니다.

완전히 반대 모양이 된다는 것은 해당 열을 뒤집기만 하면 목표하는 보드판을 만들 수 있기 때문입니다.

 

문제에 제시된 예제를 통해서 증명해보겠습니다.

예제에선 왼쪽의 보드판을 오른쪽 보드판으로 만드는 데 최소한의 뒤집기를 사용하라 합니다.

 

여러 행중 (2행, 4행)의 조합으로 행을 먼저 뒤집습니다.

뒤집은 결과는 다음과 같습니다.

목표하는 보드판과 (2행,4행)을 뒤집은 보드판의 열을 비교합니다. 비교한 결과는 다음과 같습니다.

목표하는 보드판과 (2행,4행)을 뒤집은 보드판이 2열, 4열, 5열은 서로 반대 모양을 가지고 있고, 나머지는 일치하는 것을 확인할 수 있습니다. 서로 반대 모양을 갖고 있기 때문에 2열, 4열, 5열을 뒤집기만 하면 목표하는 보드판과 모양이 일치하게 됩니다.

 

총 (2행,4행,2열,4열,5열) 5번을 뒤집으면 목표하는 보드판을 만들 수 있게 됩니다. 

 

예제에서도 result가 5로 나와있습니다.

 

다시 한번, 풀이 순서를 정리하면 다음과 같습니다.

• 임의의 행을 뒤집습니다. O(2^n)
• 뒤집은 행을 기준으로 목표하는 보드판과 열의 모양을 비교합니다. O(N*M)
• 비교한 경우 완전히 반대되면 목표하는 보드판과 모양이 일치할 수 있다고 가정하고, 다음 단계로 넘어갑니다.
• 완전히 반대되지 않는경우 해당 경우는 목표하는 보드판과 모양이 일치할 수 없다고 판단하고, 다음 경우로 넘어갑니다.

이렇게, 그리디하게 문제를 푸는 경우 드는 시간 복잡도는 O(2^n * N * M)으로 최악의 시간 복잡도는 2^10 * 10 * 10이기 때문에 102400인 대략 100만 정도의 시간 복잡도가 들게 됩니다.

 

풀이 코드

import java.util.*;

class Solution {
    public int solution(int[][] beginning, int[][] target) {
        int answer = 0;
        
        int n = beginning.length;
        int m = beginning[0].length;
        int minFlips = Integer.MAX_VALUE;
        
        for(int mask = 0; mask < (1 << n); mask++) {
            int[][] board = new int[n][m];
            
            for(int i = 0; i < n; i++) {
                board[i] = beginning[i].clone();
            }
            
            int flipCnt = 0;
            
            // 행 뒤집기
            for(int i = 0; i < n; i++) {
                if((mask & (1 << i)) != 0) {
                    flipCnt++;
                    for(int j = 0; j < m; j++) {
                        board[i][j] ^= 1;
                    }
                }
            }
            
            for(int j = 0; j < m; j++) {
                int colDiff = 0;
                for(int i = 0; i < n; i++) {
                    if(board[i][j] != target[i][j]) {
                        colDiff++;
                    }
                }
                
                if(colDiff == n) {
                    flipCnt++;
                } else if(colDiff > 0) {
                    flipCnt = Integer.MAX_VALUE;
                    break;
                }
            }
            
            minFlips = Math.min(minFlips, flipCnt);
        }
        
        return (minFlips == Integer.MAX_VALUE) ? -1 : minFlips;
    }
}

 

순차적으로 코드를 분석 해보겠습니다.

 

 for(int mask = 0; mask < (1 << n); mask++) {

 

이 코드는 n개의 행 중 뒤집을 행을 구하는 코드입니다. 

직관적으로 1씩 더해주는 코드입니다. n=10인경우, 0부터 1024를 나타냅니다.

 

0부터 1024를 2진수로 표현해서 뒤집을 행을 선택할 수 있습니다.

1111110001
1111110010

 

일부를 발췌하면 이렇게 표현이 되는데, 1은 행을 선택한다는 의미로 0은 행을 선택하지 않는다는 의미로 보면 n개의 행 중에 뒤집을 행을 모두 선택할 수 있게 됩니다.

 

 

매번 board를 시작 board로 초기화 해줍니다.

for(int i = 0; i < n; i++) { // board 초기화
                board[i] = beginning[i].clone();
            }

 

int flipCnt = 0;
            
            for(int i = 0; i < n; i++) {
                if((mask & (1 << i)) != 0) {
                    flipCnt++;
                    for(int j = 0; j < m; j++) {
                        board[i][j] ^= 1;
                    }
                }
            }

 

if((mask & (1 << i)) != 0) {

 

해당 조건문은 mask에서 i번째 비트가 1인지 확인하는 로직입니다.

즉, 결과가 0이 아닌 경우, i번째 행을 뒤집는다는 의미를 가집니다.

 

하나의 예시로 알아보겠습니다.

 

mask가 1010이라고 가정을합니다.
맨 오른쪽 부터 1번째행, 2번째행, 3번째행, 4번째 행일때, i가 변함에따라 어떻게 되는지 확인 해보겠습니다.

 

for(int j = 0; j < m; j++) {
                        board[i][j] ^= 1;
                    }

 

해당 반복문은 모든 칸을 뒤집는 부분입니다. ^= 1은 XOR 연산으로, 0과 1을 바꿔주는 역할을 합니다.

 

for(int j = 0; j < m; j++) { // 열
                int colDiff = 0;
                for(int i = 0; i < n; i++) {
                    if(board[i][j] != target[i][j]) {
                        colDiff++;
                    }
                }
                
                if(colDiff == n) {
                    flipCnt++;
                } else if(colDiff > 0) {
                    flipCnt = Integer.MAX_VALUE;
                    break;
                }
            }
     minFlips = Math.min(minFlips, flipCnt)
 }

 

행을 뒤집은 board에 각 열을 완전 탐색하면서, 목표하는 보드의 열의 모양이랑 완전히 반대되는지 확인해주는 로직입니다.

만약에 하나라도 반대되는 모양이 아닌경우, Integer.MAX_VALUE를 할당해서,  Math.min을 통해 해당 경우를 제외시켜 줍니다.

 

시간 복잡도

O(2^n * n * m)

 

최악의 시간 복잡도는 2^10 * 10 * 10으로 102400가 됩니다.

 

출력 결과