title: "[프로그래머스] 2차원 동전 뒤집기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/131703"
description: "프로그래머스 Level 3 문제 [2차원 동전 뒤집기]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import math
def fliprow(board, bits):
    flipped = []
    for i in range(len(board)):
        # i번째 row를 뒤집어야 하면 뒤집은 리스트를 저장합니다.
        if bits & (1 << i):
            flipped.append([1-x for x in board[i]])
        else:
            flipped.append(board[i])
    return flipped

def try_flipcol(board, target):
    n_colflip = 0
    # i번쨰 컬럼을 확인하는데
    for i in range(len(board[0])):
        # 경우의 수는 세가지입니다.
        # 1. 안 뒤집어도 되는 경우
        if [row[i] for row in board] == [t[i] for t in target]:
            continue
        # 2. 뒤집으면 같아지는 경우
        elif [1-row[i] for row in board] == [t[i] for t in target]:
            n_colflip += 1
        # 3. 어떻게 해도 같아질 수 없는 경우
        else:
            return -1
        
    return n_colflip

def solution(beginning, target):
    # 뒤집어야 하는 row를 비트로 표현합니다.
    # n개의 row가 있으면 0~2**n-1 까지 수로 나타내면 됩니다.
    n = len(beginning)
    ans = math.inf
    for bits in range(2**n):
        flipped = fliprow(beginning[:], bits)
        n_colflip = try_flipcol(flipped, target)
        if n_colflip == -1:
            continue
            
        n_rowflip = sum(bits & (1 << i) != 0 for i in range(n))
        ans = min(n_rowflip + n_colflip, ans)

    return ans if ans != math.inf else -1

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges