[코테] 백준 그리디 14939번 문제

14939번 : 불 끄기

문제 링크

https://www.acmicpc.net/problem/14939

문제 설명

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

입력

10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.

출력

모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.

문제 풀이

해결 방법을 아무리 고민해봐도 떠오르지 않아 인터넷 검색을 통해서 해결하였다..

이런 생각을 하기까지 얼마나 많은 문제들을 풀어봐야할까? 힘내보자!

1. 핵심은 맨 윗줄의 경우 모든 경우의 수(2의 10제곱)를 스위치를 누르고,
2. 두번째줄부터는 바로 위의 전구가 눌려있으면 버튼을 누르는 식으로 반복한다.
3. 그 결과 맨 마지막줄의 전구가 다 꺼졌으면 모든 전구가 다 꺼진것이므로 스위치를 누른 횟수를 출력한다.

from copy import deepcopy

matrix = [[*map(lambda x: 1 if x == 'O' else 0, input())] for _ in range(10)]
di, dj = [1, -1, 0, 0, 0], [0, 0, 1, -1, 0]
answer = float('inf')

def press_button(i, j) :
    global copy_matrix
    for k in range(5) :
        ni, nj = i + di[k], j + dj[k]
        if 0 <= ni < 10 and 0 <= nj < 10 :
            copy_matrix[ni][nj] ^= 1
            
for case in range(1 << 10) :
    copy_matrix = deepcopy(matrix)
    count = 0
    
    for j in range(10) :
        if case & (1 << j) :
            press_button(0, j)
            count += 1
            
    for i in range(1, 10) :
        for j in range(10) :
            if copy_matrix[i-1][j] : 
                press_button(i, j)
                count += 1
                
    if sum(copy_matrix[10-1]) == 0 :
        answer = min(answer, count)
        
print(answer if answer != float('inf') else -1)