[PG] 2차원 동전 뒤집기

beginning 에서 target 으로 가려고 한다.
우선 바꿔져야 하는 곳을 1로 표현해보면 아래와 같이 change_spot을 만들 수 있다.

change_spot을 만들어보면 특징을 볼 수 있는데, 행 별로 서로 같거나, 반전된 비트이다.

1	0	1	1	1
0	1	0	0	0
1	0	1	1	1
0	1	0	0	0
0	1	0	0	0

이를 우선적으로 체크해서 만약 같거나 반전되지 않는 경우가 있다면 -1을 return 하고, 그렇지 않다면 된다는 가정 하에 최소 경우의 수를 찾는다.

def solution(beginning, target):
    answer = 0
    row = len(beginning[0]); col = len(beginning) #열, 행
    
    change_spot = [['0' for _ in range(row)] for _ in range(col)]
    
    for i in range(col):
        for j in range(row):
            if beginning[i][j]!=target[i][j]:
                change_spot[i][j]='1'
    standard = '0'
    for a in change_spot:
        if '1' in a:
            standard=''.join(a)
            break;
    for b in change_spot:
        compare = int(''.join(b),2)^int(standard,2)
        if compare == 0 or compare == 2**(len(change_spot[0]))-1:
            continue
        else: 
            return -1
    #일단 된다는 가정하에 최소 찾기
    answer_1 = 0; str_1='';
    answer_2 = 0; str_2='';
    for b in change_spot:
        compare = int(''.join(b),2)^int(standard,2)
        if compare == 0:
            answer_1 +=1
            str_1=b
        else:
            answer_2+=1
            str_2=b
    #print(answer_1, str_1, answer_2, str_2)
    # 0으로 만든다. 이 때 다른 쪽 애를 바꿔야 함
    for i in str_1: 
        if i=='1':
            answer_2+=1
    for j in str_2:
        if j=='1':
            answer_1+=1
            
    return min(answer_1, answer_2)

우리의 목표는 이 1들을 모두 0으로 만들어주기 위함이므로 일단 행부터 반전시키는 경우를 찾는다.
위의 경우라면 10111 또는 01000 으로 만들어주는 각각의 경우의 수를 찾고, 그 후에 이제 이 행에서 모두를 0으로 만드는 경우의 수를 각각 더해준다.