Question

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

Explanation

For 2차원 동전, bitmask iterating through just 1«rows does not travel all the possibilities. 1«rows is just a single bitmask where leftmost bit is 1 and to its right is all 0. We should instead do range(1«rows) which now considers all bitmasks with row bits.

Also for this question, do a test case as to whether doing row then col or col then row matters (does order matter)? Turns out order doesn’t matter but let’s just do row then col.

def flipColumn(arr, col):
    n = len(arr)

    for i in range(n):
        if arr[i][col] == 1:
            arr[i][col] = 0
        else:
            arr[i][col] = 1


def solution(begin, target):
    answer = float("inf")
    rows = len(begin)
    cols = len(begin[0])

    # Initialize the flipped matrix with the correct size
    flipped = [[0 for _ in range(cols)] for _ in range(rows)]

    # Fill the flipped matrix with the flipped values of the begin matrix
    for i in range(rows):
        for j in range(cols):
            if begin[i][j] == 0:
                flipped[i][j] = 1
            else:
                flipped[i][j] = 0

    for unit in range(1 << rows):
        count = 0
        rowsFlipped = []
        for i in range(rows):
            comp = 1 << i
            if unit & comp:
                rowsFlipped.append(flipped[i][:])
                count += 1
            else:
                rowsFlipped.append(begin[i][:])

        for j in range(cols):
            curCol = []
            targetCol = []
            for i in range(rows):
                curCol.append(rowsFlipped[i][j])
                targetCol.append(target[i][j])

            # 현재 column과 target column이 다르면 뒤집기
            if curCol != targetCol:
                flipColumn(rowsFlipped, j)
                count += 1
        if rowsFlipped == target:
            answer = min(answer, count)
    if answer == float("inf"):
        answer = -1

    return answer