[Baekjoon] 14939번 : 불 끄기

1. 문제

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

• DP 문제

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

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

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

// 예제 입력 1 
#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#

// 예제 출력 1 
4

2. 핵심 아이디어

3. Python 문제풀이

import sys
input = sys.stdin.readline

t = []
for i in range(10) :
  tmp = list(input().rstrip())
  for j in range(10) :
    if tmp[j] == 'O' :
      tmp[j] = True 
      continue
    tmp[j] = False
  t.append(tmp)
 
dx = [-1, 1, 0, 0, 0]
dy = [0, 0, 0, -1, 1]
result = 101

for f in range(1 << 10) :
  a = []
  for i in range(10) :
    a.append(t[i][:])
  cnt = 0

  for i in range(10) :
    if f & (1 << i) :
      cnt += 1
      for k in range(5) :
        nx = i + dx[k]
        ny = 0 + dy[k]
        if 0 <= nx <= 9 and 0 <= ny <= 9:
          a[ny][nx] = not a[ny][nx]

  for i in range(1, 10) :
    for j in range(10) :
      if not a[i-1][j] :
        continue
      for k in range(5) :
        nx = j + dx[k]
        ny = i + dy[k]
        if 0 <= nx <= 9 and 0 <= ny <= 9 :
          a[ny][nx] = not a[ny][nx]
      cnt += 1


  c = True
  for i in range(10) :
    if a[9][i] == True :
      c = False

  if c :
    result = min(cnt, result)
 
print(result if result != 101 else -1)

4. Java 문제풀이