2차원 동전 뒤집기 (Python)

접근 방법

1. target 보드 위에 beginning을 덮는다고 생각해보면 (XOR 연산), 어느 돌을 뒤집어야할지 표시하는 것과 비슷한 효과를 보인다.
2. 같은 행 및 열을 두번 뒤집으면 안뒤집은 것과 마찬가지다. 열과 행은 한번씩만 뒤집으면 된다.
3. 각 행을 기준으로 순회를 하며, 그 행과 똑같은 행이면 넘어가고 뒤집은 것과 비슷한 행은 뒤집어주고 뒤집은 갯수를 1을 추가한다. 두 조건 모두 만족하지 못한다면 정답을 찾을 수 없는 경우이기 때문에 바로 -1을 반환해준다.
   
   1. 여기서 해당 행에 1이 있다면 다시 뒤집어야 한다는 것이기 때문에 행을 뒤집은 것 + 행에 있는 1의 갯수를 기준으로 최소 값을 반환하면 정답이다.

코드

def solution(beginning, target):
    xor = [[0] * len(beginning[0]) for _ in range(len(beginning))]
    for i in range(len(beginning)):
        for j in range(len(beginning[0])):
            if beginning[i][j] != target[i][j]:
                xor[i][j] = 1
            else:
                xor[i][j] = 0
    
    minimum = 1_000_000
    base_row = xor[0]
    for row in xor:
        diff = 0
        for other_row in xor:
            if row == other_row: continue
            
            temp_row = [1 - i for i in other_row]
            if row == temp_row:
                diff += 1
                continue
            
            return -1
        
        diff += sum(row)
        if diff < minimum:
            base_row = row
            minimum = diff
    
    return minimum

복기