코딩 테스트 - 2차원 동전 뒤집기

2차원 동전 뒤집기

문제 링크 : 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은 동전의 뒷면을 의미합니다.

입출력 예

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

풀이 방법

• 문제의 동전 뒤집기는 행, 열 전체를 뒤집어야 되는데, 이는 순서와는 상관없고 특정 행을 뒤집는다고 지정하면 자동으로 뒤집어야 되는 열이 정해진다. 특정 행을 선택하기 위해서 dfs를 통해서 브루트포스로 모든 케이스를 검사했다.
• 특정 행을 뒤집고 난 다음에 첫 번째 행을 기준으로 타겟과 그 열의 값이 다른 경우 뒤집고 난 다음에 이것이 타겟과 동일한 경우에만 횟수 비교를 진행했다.
  -> 해당 문제풀이는 O((2^N)*N*M)의 시간복잡도가 걸리고, N과 M은 최대 10의 값을 가지기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>
#include <climits>

using namespace std;

int minCount = INT_MAX;
int row, col;

void dfs(int r, int count, vector<vector<int>> board, vector<vector<int>>& target){
    if (r == row){
        // 첫 번째 행을 기준으로 값이 다르면 그 열 뒤집기
        for(int j = 0; j < col; j++){
            if (board[0][j] != target[0][j]){
                count++;
                for(int i = 0; i < row; i++){
                    board[i][j] ^= 1;
                }
            }
        }
        
        if (board == target){
            minCount = min(minCount, count);
        }
        return;
    }
    
    // r번째 행을 뒤집지 않기
    dfs(r + 1, count, board, target);
    
    // r번째 행을 뒤집기
    for(int j = 0; j < col; j++){
        board[r][j] ^= 1;
    }
    dfs(r + 1, count + 1, board, target);
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    row = beginning.size();
    col = beginning[0].size();
    
    dfs(0, 0, beginning, target);
    
    return (minCount == INT_MAX ? -1 : minCount);
}