[프로그래머스: 2차원 동전 뒤집기(Python)]

문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

 

유형 

• 완전탐색 
• 비트마스킹

 

접근 방법 

• 각각의 행과 열은 뒤집거나 or 안뒤집는 경우 2가지 뿐이고, 전체 보드가 이룰 수 있는 모양의 경우의 수는 2^(row+col)이다.
• 모든 가능한 행 조합과 모든 열 조합에 대해 탐색하면 시간초과 발생, 따라서 일단 뒤집을 행을 선택 후 뒤집은 상태에서 target과 다른 열만 뒤집어 target과 보드가 같아지는지 확인한다. 
• 이때, 뒤집을 행의 선택은 비트마스킹을 이용해 시간을 줄인다.

 

시행 착오

시간 초과 문제로 첫 풀이는 실패했다. 

 

sol1: 뒤집을 행 선택, 뒤집을 열 선택 -> 뒤집어보고 target과 비교 -> 시간초과 (너무 많은 탐색), 모든 경우의 수에 대해 탐색 수행 

sol2: 뒤집을 행 선택후, 뒤집고 -> target과 다른 col만 선택해서 뒤집은 뒤 target과 비교 -> 단일 for, 탐색횟수 대폭 감소

 

시간초과를 줄이기 위해서는 반복하는 횟수를 줄이는 방법을 생각해보자!!

 

구현 코드 

## 완전탐색, 비트마스킹
import copy 
def flipCol(board, n, m, col):
    for i in range(n):
        board[i][col] ^= 1
    
    return board 

def solution(beginning, target):
    answer = int(1e9)
    
    n, m = len(beginning), len(beginning[0])
    
    flipped = [] #뒤집은 보드를 미리 계산 후, 행을 뒤집는 반복 시행의 연산을 줄인다 
    for i in range(n):
        tmp = []
        for j in range(m):
            if beginning[i][j]==0:
                tmp.append(1)
            else:
                tmp.append(0)
        flipped.append(tmp)
    
    for bit1 in range(1<<n): #뒤집을 행 비트마스킹을 이용해 선택 
        # 행 뒤집기 
        board = []
        cnt = 0 
        for i in range(n): 
            if bit1 & (1<<i): #선택된 행 
                cnt += 1
                board.append(list(flipped[i][:]))
            else:
                board.append(list(beginning[i][:]))
        
        #열 뒤집기
        for j in range(m):
            tmp_col = []
            target_col = [] 
            for i in range(n):
                tmp_col.append(board[i][j])
                target_col.append(target[i][j])
            
            #target과 다른 col만 뒤집어줌 
            if tmp_col != target_col:
                board = flipCol(board, n, m, j)
                cnt += 1

        if board == target:
            answer = min(answer, cnt)
                
                    
    if answer == int(1e9):
        return -1 
    
    return answer