[백준 14927번] 전구 끄기 (Python3)

import sys,copy
input = sys.stdin.readline
dy = [0,1,-1,0,0]; dx = [0,0,0,1,-1]

def switch(y,x,board):
  for i in range(5):
    y1,x1 = y+dy[i],x+dx[i]
    if N>y1>=0 and N>x1>=0:
      board[y1][x1] ^= 1

def bitmask(bit):
  global result
  newboard = copy.deepcopy(board)
  cnt = 0
  for x in range(N):
    if bit&(1<<x):
      switch(0,x,newboard); cnt += 1
  for y in range(N):
    for x in range(N):
      if newboard[y][x]:
        if y==N-1:
          return
        switch(y+1,x,newboard); cnt += 1
  result = min(result,cnt)

def solve():
  for bit in range(1<<N):
    bitmask(bit)

N = int(input())
board = [[*map(int,input().split())] for i in range(N)]
result = 1e9; solve()
print(result if result!=1e9 else -1)

불끄기 [백준 14939번] 불 끄기 (Python3) (tistory.com) 문제에서 N의 범위만 확장되었다.

이전의 DFS 브루트포스 풀이방식으로 제출하자 시간초과가 발생하여 이번엔 비트를 이용하였다.

 

풀이를 설명하면,

1. 가장 첫번째 줄을 켜고끄는 것을 모든 경우의 수에 대해서 해본다.

2. 나머지 줄은 현재 줄의 윗줄의 불에 따라 결정한다.

3. 마지막 줄이 모두 꺼져있으면 횟수를 갱신한다.

 

이때 틀렸습니다!가 발생하였는데, 3번에서 마지막 줄이 모두 꺼져있으면 결과를 출력하도록 코드를 짜면 틀리게 된다.

이유는 모든 불을 끄는 경우의 수가 유일하지 않아 최솟값으로 출력해야하기 때문이다.

그런데 이상한 점은 이전의 불끄기 문제 (N=10 고정)에 똑같은 코드를 제출하자 맞았습니다 가 떴다.

불끄기 문제의 데이터가 약한 탓인지 아니면 N=10일때는 유일해를 갖지만 N이 다른 경우에는 그렇지 않은 것인지 모르겠다.

 

발견한 유일하지 않은 경우의 수는 N=4 1111/1111/1111/1111 이 있다. 최솟값은 4이지만 10도 가능하다.

 

 

오늘의 교훈) 증명할 수 없다면 단정짓지 말자