[Programmers] Q131703 2차원 동전 뒤집기

[Programmers] Q131703 2차원 동전 뒤집기

Question

Language: Python

이번 문제는 row/col에 대해서 동전을 일괄적으로 뒤집었을 때 목표한 상태를 만들 수 있는 지 여부를 판별하는 문제이다.

그래서, 우선적으로 모든 row에 대한 조합을 분석한 후, column에 대한 분석을 진행한다. row를 뒤집는 경우는, row을 뒤집지 않는 경우 + row을 1개만 뒤집는 경우 + …row을 n개 뒤집는 경우로, 최대 1024개의 조합을 조사하면 된다.

_nC₀+_nC₁+_nC₂…+_nC_n

이를 쉽게 하기 위해 bitmasking을 통해 모든 조합을 고려할 수 있다.

for i in range(1<<n_rows):
    row_flip=[]
    flip_count=0
    
    for row in range(n_rows):
        if (1<<row) & i:
            row_flip.append(flipped_rows[row][:])
            flip_count+=1
        else:
            row_flip.append(beginning[row][:])

그런 다음 각각의 경우에 대해서 column 뒤집기를 수행하면 된다.

for col in range(n_cols):
    for row in range(n_rows):
        if row_flip[row][col] != target[row][col]:
            flip_column(row_flip,n_rows,col)
            flip_count+=1
            break

Solution

from math import inf
def flip_column(arr,n_rows,col):
    for row in range(n_rows):
        if arr[row][col]:
            arr[row][col]=0
        else:
            arr[row][col]=1

def solution(beginning, target):
    answer = inf
    
    n_rows=len(beginning)
    n_cols=len(beginning[0])
    
    flipped_rows=[]
    flip_count=0
    
    
    for row in range(n_rows):
        temp_row=[]
        for col in range(n_cols):
            if beginning[row][col]==0:
                temp_row.append(1)
            else:
                temp_row.append(0)
        flipped_rows.append(temp_row)
        
    for i in range(1<<n_rows):
        row_flip=[]
        flip_count=0
        
        for row in range(n_rows):
            if (1<<row) & i:
                row_flip.append(flipped_rows[row][:])
                flip_count+=1
            else:
                row_flip.append(beginning[row][:])
        
        
        for col in range(n_cols):
            for row in range(n_rows):
                if row_flip[row][col] != target[row][col]:
                    flip_column(row_flip,n_rows,col)
                    flip_count+=1
                    break
        
        if row_flip==target:
            answer=min(answer,flip_count)

    return answer if answer != inf else -1