[Algorithm] Programmers :: 2차원 동전 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

int answer = 0x3f3f3f3f;
vector<vector<int>> board;
vector<vector<int>> targetBoard;
 
int compareCol(int col)
{
    int count = 0;
    for (int i = 0; i < board.size(); ++i)
    {
        if (board[i][col] == targetBoard[i][col])
        {
            ++count;
        }
    }
 
    if (count == board.size()) return 0;
    if (count == 0) return 1;
    
    return -1;
}
 
void FlipRow(int r)
{
    for (int i = 0; i < board[0].size(); ++i)
    {
        board[r][i] = !board[r][i];
    }
}
 
 
void DFS(int row, int rowFlipCount)
{
    if (row == board.size())
    {
        // 체크.
        int count = 0;
        for (int i = 0; i < board[0].size(); ++i)
        {
            int result = compareCol(i);
 
            if (result == -1) return;
            count += result;
        }
 
        answer = min(answer, count+rowFlipCount);
 
        return;
    }
 
    DFS(row + 1, rowFlipCount);
    FlipRow(row);
    DFS(row + 1, rowFlipCount + 1);
    FlipRow(row);
}
 
 
int solution(vector<vector<int>> beginning, vector<vector<int>> target) 
{
    board = beginning;
    targetBoard = target;
    
    DFS(0, 0);
 
    if (answer == 0x3f3f3f3f) return -1;
    return answer;
}

Lv3문제에는 그리디 + 탐색유형이 꽤 많은 것 같다.

이것도 이전문제와 굉장히 비슷한 느낌의 문제이다. 탐색을 시도하되, 필요한 부분만 우선적으로 탐색하는 것이다.

이번 문제같은 경우는 그냥 행을 뒤집,안뒤집 케이스를 탐색하면서 열을 전부 검사하면 된다.

 

열을 검사할 때 타겟과 전부같거나 전부다르면 타겟으로 만들 수 있다. (전부 다르면 뒤집으면 되니까)

단 일부분만 다를 경우는 타겟으로 만들 수 없기 때문에 그냥 그대로 해당케이스를 return시키면 된다.

뒤집,안뒤집는것만 따지기때문에 bit로 풀 수도 있다.