Lv.3 2차원 동전 뒤집기 [C++]

문제 링크

성공 여부(걸린 시간): 71.4점 실패 → 정답 (총 43분 33초)

아이디어

처음에는 그리디하게 열 기준으로 진행했다.

• 1열을 먼저 맞추기 위해 필요한 행을 전부 뒤집고
• 이후 각 열마다
  • 전부 같으면 그대로
  • 전부 다르면 열 토글
  • 섞여 있으면 불가능

이런 식으로 처리했다.

하지만 실패 원인은 명확했다.

첫 열에서 무조건 행을 뒤집는 선택을 해버리면서
가능한 해의 절반을 날리고 시작한 것.

 

왜 그리디가 안 되는가?

 

이 문제는 단순 구현 문제가 아니라
XOR 조건을 만족하는 행/열 선택 문제다.

행을 뒤집었는지 여부를 r[i], 열을 뒤집었는지 여부를 c[j] 라고 하면

최종 상태는

beginning[i][j] XOR r[i] XOR c[j]

가 된다.

 

우리가 원하는 것은 이것이 target[i][j] 와 같아지는 것.

따라서 조건은

r[i] XOR c[j] = beginning[i][j] XOR target[i][j]

여기서

diff[i][j] = beginning[i][j] XOR target[i][j]

라고 두면 최종 식은

r[i] XOR c[j] = diff[i][j]

이 된다.

---

⭐ 핵심 포인트

이 식의 자유도는 사실상 1비트뿐이다.

왜냐하면:

• c[0] 을 0으로 둘지
• c[0] 을 1로 둘지

이 두 경우만 존재하고,
이 값이 정해지면 나머지 r과 c는 전부 강제로 결정된다.

즉,

경우의 수는 2개뿐이다.

그래서 c[0] = 0 / 1 두 번만 검사하면 모든 해를 다 보는 것과 같다.

---

풀이 코드

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> beginning, vector<vector<int>> target) {

    int n = beginning.size();        // 행 개수
    int m = beginning[0].size();     // 열 개수

    // diff[i][j] = 해당 칸을 맞추기 위해
    // "행토글 XOR 열토글" 값이 되어야 하는 값
    // (beginning과 target이 다르면 1, 같으면 0)
    vector<vector<int>> diff(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            diff[i][j] = beginning[i][j] ^ target[i][j];

    const int INF = 1e9;
    int answer = INF;

    // c[0] (첫 번째 열을 뒤집을지 말지)는
    // 0 또는 1 두 경우만 존재
    for (int firstCol = 0; firstCol <= 1; firstCol++) {

        vector<int> r(n);   // 각 행 뒤집기 여부
        vector<int> c(m);   // 각 열 뒤집기 여부

        c[0] = firstCol;

        // 1️⃣ 첫 번째 열 기준으로 r[i] 결정
        // r[i] XOR c[0] = diff[i][0]
        // → r[i] = diff[i][0] XOR c[0]
        for (int i = 0; i < n; i++) {
            r[i] = diff[i][0] ^ c[0];
        }

        // 2️⃣ 첫 번째 행 기준으로 c[j] 결정
        // r[0] XOR c[j] = diff[0][j]
        // → c[j] = diff[0][j] XOR r[0]
        for (int j = 0; j < m; j++) {
            c[j] = diff[0][j] ^ r[0];
        }

        // 3️⃣ 전체 검증
        // 모든 칸에서 r[i] XOR c[j] == diff[i][j] 이어야 함
        bool possible = true;
        for (int i = 0; i < n && possible; i++) {
            for (int j = 0; j < m; j++) {
                if ((r[i] ^ c[j]) != diff[i][j]) {
                    possible = false;
                    break;
                }
            }
        }

        // 4️⃣ 가능하면 뒤집기 횟수 계산
        if (possible) {
            int flipCount = 0;

            for (int i = 0; i < n; i++)
                flipCount += r[i];

            for (int j = 0; j < m; j++)
                flipCount += c[j];

            answer = min(answer, flipCount);
        }
    }

    return (answer == INF) ? -1 : answer;
}