2차원 동전 뒤집기(미해결)

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

풀이(미해결)

1. beginning 과 target 을 비교해 같으면 0, 다르면 1인 board 배열 만듦.
2. board의 행부터 1인 부분을 돌리고, 그 다음에 아직 1인 부분이 남아있으면 열을 돌림.
3. board의 열부터 1인 부분을 돌리고, 그 다음에 아직 1인 부분이 남아있으면 행을 돌림.

• 1이 남아있다면 target이 불가능한 배열. -1을 리턴.

4. 2번과 3번 중 돌린 sum이 적은 값을 리턴.

if (board[i][j] == 1)
{
	for (int k = 0; k < M; ++k) board[i][k] = (board[i][k] == 1 ? 0 : 1);
    	++sum;
        break;
}

루프 구문의 break를 빼면 target 배열이 나오는데 break를 넣으면 target이 안된다.
같은 행이나 열을 여러 번 돌리는 게 의미가 있나? 어디가 틀렸을까?

#include <string>
#include <vector>

using namespace std;

int board[11][11];
int N, M;

int change_raw_col()
{
    int sum = 0;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (board[i][j] == 1)
            {
                for (int k = 0; k < M; ++k) board[i][k] = (board[i][k] == 1 ? 0 : 1);
                ++sum;
                break;
            }
        }
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (board[i][j] == 1)
            {
                for (int k = 0; k < N; ++k) board[k][j] = (board[k][j] == 1 ? 0 : 1);
                ++sum;
                break;
            }
        }
    }

    return sum;
}

int change_col_raw()
{
    int sum = 0;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (board[i][j] == 1)
            {
                for (int k = 0; k < N; ++k) board[k][j] = (board[k][j] == 1 ? 0 : 1);
                ++sum;
                break;
            }
        }
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (board[i][j] == 1)
            {
                for (int k = 0; k < M; ++k) board[i][k] = (board[i][k] == 1 ? 0 : 1);
                ++sum;
                break;
            }
        }
    }

    return sum;
}
int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 0;
    N = (int)target.size();
    M = (int)target[0].size();

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (beginning[i][j] == target[i][j]) board[i][j] = 0;
            else board[i][j] = 1;
        }
    }

    int mini = change_raw_col();

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (beginning[i][j] == target[i][j]) board[i][j] = 0;
            else board[i][j] = 1;
        }
    }

    answer = change_col_raw();

    answer = min(answer, mini);
    printf("%d", answer);

    return answer;  
}

---

풀이(61.9점)

완전 탐색을 활용... 어디가 틀렸을까?

1. 1행 뒤집기, 1열 뒤집기, 1행 뒤집기, 1열 뒤집지 않기, 1행 뒤집지 않기, 1열 뒤집기, 1행 뒤집지 않기, 1열 뒤집지 않기...
2. 가다가 target이 되면 sum return;
3. ~행, ~열이 N, M일 때 mini가 2147000000이면 target 안 됨.

#include <string>
#include <vector>

using namespace std;

// 1행 뒤집기, 1열 뒤집기.
// 1행 뒤집기, 1열 뒤집지 않기.
// 1행 뒤집지 않기, 1열 뒤집기.
// 1행 뒤집지 않기, 1열 뒤집지 않기...
// 가다가 target이 되면 sum return;
// ~행, ~열이 N, M이 되면 -1;

int N, M, board[11][11], mini = 2147000000;

void DFS(int board[11][11], int r, int c, int sum)
{
    // target과 같나 확인.
    bool flag = true;
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            if(board[i][j])
            {
                flag = false;
                break;
            }
        }
        if(!flag) break;
    }
    
    if(flag)
    {
        if(mini > sum)
            mini = sum;
    }
    else if(r == N && c == M) return;
    else
    {
        r = min(r, N - 1);
        c = min(c, M - 1);
        // r행 뒤집기, c열 뒤집지 않기.
        for(int k = 0; k < M; ++k) board[r][k] = 1 - board[r][k];
        DFS(board, r + 1, c + 1, sum + 1);
        // r행 뒤집기, c열 뒤집기.
        for(int k = 0; k < N; ++k) board[k][c] = 1 - board[k][c];
        DFS(board, r + 1, c + 1, sum + 1);
        // r행 뒤집지 않기, c열 뒤집기.
        for(int k = 0; k < M; ++k) board[r][k] = 1 - board[r][k];
        DFS(board, r + 1, c + 1, sum + 1);
        // r행 뒤집지 않기, c열 뒤집지 않기.
        for(int k = 0; k < N; ++k) board[k][c] = 1 - board[k][c];
        DFS(board, r + 1, c + 1, sum + 1);
    }
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 0;
    N = beginning.size();
    M = beginning[0].size();
    
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            if(beginning[i][j] == target[i][j]) board[i][j] = 0;
            else board[i][j] = 1;
        }
    }
    
    // r, c, sum;
    DFS(board, 0, 0, 0);
    if(mini == 2147000000) mini = -1;
    
    return answer = mini;
}

---

풀이

뒤집거나 뒤집지 않을 때 sum + a의 값을 다 1 더하다니... 바보다. 뒤집지 않을 때는 0, 둘 다 뒤집을 때는 2, 행이나 열만 뒤집을 때는 1을 더해야 한다.

#include <string>
#include <vector>

using namespace std;

// 1행 뒤집기, 1열 뒤집기.
// 1행 뒤집기, 1열 뒤집지 않기.
// 1행 뒤집지 않기, 1열 뒤집기.
// 1행 뒤집지 않기, 1열 뒤집지 않기...
// 가다가 target이 되면 sum return;
// ~행, ~열이 N, M이 되면 -1;

int N, M, board[11][11], mini = 2147000000;

void DFS(int board[11][11], int r, int c, int sum)
{
    // target과 같나 확인.
    bool flag = true;
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            if(board[i][j])
            {
                flag = false;
                break;
            }
        }
        if(!flag) break;
    }
    
    if(flag)
    {
        if(mini > sum)
            mini = sum;
    }
    else if(r == N && c == M) return;
    else
    {
        r = min(r, N - 1);
        c = min(c, M - 1);
        // r행 뒤집기, c열 뒤집지 않기.
        for(int k = 0; k < M; ++k) board[r][k] = 1 - board[r][k];
        DFS(board, r + 1, c + 1, sum + 1);
        // r행 뒤집기, c열 뒤집기.
        for(int k = 0; k < N; ++k) board[k][c] = 1 - board[k][c];
        DFS(board, r + 1, c + 1, sum + 2);
        // r행 뒤집지 않기, c열 뒤집기.
        for(int k = 0; k < M; ++k) board[r][k] = 1 - board[r][k];
        DFS(board, r + 1, c + 1, sum + 1);
        // r행 뒤집지 않기, c열 뒤집지 않기.
        for(int k = 0; k < N; ++k) board[k][c] = 1 - board[k][c];
        DFS(board, r + 1, c + 1, sum);
    }
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 0;
    N = beginning.size();
    M = beginning[0].size();
    
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            if(beginning[i][j] == target[i][j]) board[i][j] = 0;
            else board[i][j] = 1;
        }
    }
    
    // r, c, sum;
    DFS(board, 0, 0, 0);
    if(mini == 2147000000) mini = -1;
    
    return answer = mini;
}

---

이해 안되는 부분이 있다. r행을 뒤집지 않고, c열을 뒤집지 않을 때의 DFS(board, r+1, c+1, sum)을 맨 위에 두면 틀린다. 왜? 이유 알아내기.

else
    {
        r = min(r, N - 1);
        c = min(c, M - 1);
        // r행 뒤집지 않기, c열 뒤집지 않기.
        // 여기에 두면 틀린다.
        DFS(board, r + 1, c + 1, sum);
        // r행 뒤집기, c열 뒤집지 않기.
        for(int k = 0; k < M; ++k) board[r][k] = 1 - board[r][k];
        DFS(board, r + 1, c + 1, sum + 1);
        // r행 뒤집기, c열 뒤집기.
        for(int k = 0; k < N; ++k) board[k][c] = 1 - board[k][c];
        DFS(board, r + 1, c + 1, sum + 2);
        // r행 뒤집지 않기, c열 뒤집기.
        for(int k = 0; k < M; ++k) board[r][k] = 1 - board[r][k];
        DFS(board, r + 1, c + 1, sum + 1);
        // 이 코드에서 맞기 위해서는 아래의 이 작업이 꼭 필요하다.
        // 왜 굳이 원래 board로 만들어야 할까?
        //for(int k = 0; k < N; ++k) board[k][c] = 1 - board[k][c];
    }