[백준 14939번] 파이썬 - 불끄기

백준 14939 - 불 끄기

시간 제한 1초, 메모리 제한 256MB

# 조건

• 전구 100개가 10×10 정사각형 모양으로 늘어서 있다.
• 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다.
• 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라

# 접근 방법

• 브루트 포스와 그리디를 활용하여 비트마스킹으로 풀어줘야 하는 문제였다.. 비트마스킹으로 첫 줄의 모든 경우의 수를 구하는 아이디어가 잘 생각이 나지 않아 다른 블로그를 참고하였다.
  https://bio-info.tistory.com/234

• 핵심은 첫 행의 전구 10개에 대해 켜고 끄는 모든 경우의 수 2 ^ 10 = 1024개에 대하여, 두 번째 행부터는 윗 행의 전구가 켜져 있는 경우에만 스위치를 누르는 것이다.

• 처음에 전구 배열을 arr에 받고, 스위치를 눌릴 경우 편하게 바꿔주기 위하여 True와 False로 변경 해주었습니다.

• 이 때, 최중 출력 값으로 사용할 result를 101로 초기화하는데 이 이뉴는 스위치 개수가 최대 100개 여서 누른 스위치 개수의 최소값이 101이 될 수 없기 때문입니다.

• 스위치를 누르는 경우의 수를 0에서 1023까지 ck로 받은 후, deepcopy를 이용하여 처음 배열을 복사해줍니다.

  • 여기서 1023를 이진수로 받는다면 모든 전구에 대해 켜지고 꺼지는 경우의 수까지 고려할 수 있기 때문입니다!

• 이후, 첫 행의 스위치를 누르는 경우를 k & (1<<j)로 반영해줍니다.

  • 또한 첫 행의 스위치를 눌렀을 경우 주변 스위치에 대한 행동을 반영해줍니다.

• 2번째 행부터 바로 윗 행의 스위치가 켜져있다면 스위치를 눌리면서 cnt를 + 해줍니다.

  • 이후 10번째 행에 모든 전구의 불이 꺼져있다면 최소값을 비교하여 갱신해주면 됩니다.

import sys  

sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from copy import deepcopy  

di, dj = [-1, 1, 0, 0, 0], [0, 0, 0, -1, 1]  
result = 101  
arr = [[False] * 10 for _ in range(10)]  
for i in range(10):  
    a = input()  
    for j in range(10):  
        if a[j] == 'O':  
            arr[i][j] = True  

# 첫 줄의 모든 경우의 수  
for ck in range(1 << 10):  
    new_arr = deepcopy(arr)  
    cnt = 0  
    # 첫줄에 10개 전구 하나씩 탐색  
    for k in range(10):  
        # j번째 스위치를 누른다면 +1  
        if ck & (1 << k):  
            cnt += 1  
            # 맨윗줄 방향 살피기  
            for d in range(5):  
                ni, nj = 0+di[d], k + dj[d]  
                if 0<=ni<=9 and 0 <= nj <= 9:  
                    new_arr[ni][nj] = not new_arr[ni][nj]  


    for i in range(1,10):  
        for j in range(10):  
            if new_arr[i-1][j] == True:  
                cnt += 1  
                for d in range(5):  
                    ni, nj = i + di[d], j + dj[d]  
                    if 0 <= ni <= 9 and 0 <= nj <= 9:  
                        new_arr[ni][nj] = not new_arr[ni][nj]  

    if all(c == False for c in new_arr[-1]):  
        result = min(result, cnt)  
print(result if result < 101 else -1)