import sys
input = sys.stdin.readline
dy = [0,1,0,-1,0]
dx = [0,0,1,0,-1]
def switch(y,x): #5방향 켜고끄기
for i in range(5):
y1,x1 = y+dy[i],x+dx[i]
if 10>y1>=0 and 10>x1>=0:
board[y1][x1] = abs(board[y1][x1]-1)
board = []
for i in range(10):
board.append([*map(lambda x:1 if x=="O" else 0,[*input().strip()])])
result = -1
def DFS(y,x,cnt):
global result
if result != -1: #결과가 나왔으면 종료
return
if x == 10:
DFS(y+1,0,cnt)
return
if y==0 and x==0:
if not board[y][x]:
DFS(y,x+1,cnt)
for i,j in [(0,1),(0,2),(1,2)]:
switch(y+dy[i],x+dx[i])
switch(y+dy[j],x+dx[j])
DFS(y,x+1,cnt+2)
switch(y+dy[i],x+dx[i])
switch(y+dy[j],x+dx[j])
else:
for i in range(3):
switch(y+dy[i],x+dx[i])
DFS(y,x+1,cnt+1)
switch(y+dy[i],x+dx[i])
for i in range(3):
switch(y+dy[i],x+dx[i])
DFS(y,x+1,cnt+3)
for i in range(3):
switch(y+dy[i],x+dx[i])
elif y==0 and x!=9:
if not board[y][x]:
DFS(y,x+1,cnt)
for i in [1,2]:
switch(y+dy[i],x+dx[i])
DFS(y,x+1,cnt+2)
for i in [1,2]:
switch(y+dy[i],x+dx[i])
else:
for i in [1,2]:
switch(y+dy[i],x+dx[i])
DFS(y,x+1,cnt+1)
switch(y+dy[i],x+dx[i])
elif y == 9:
if sum(board[9]) == 0:
result = cnt
return
else:
if not board[y][x]:
DFS(y,x+1,cnt)
else:
switch(y+1,x)
DFS(y,x+1,cnt+1)
switch(y+1,x)
DFS(0,0,0)
print(result)
접근방식을 잘못해서 오래 걸린 문제.
처음부터 태그를 안보고 푸는게 오히려 더 빨리 풀었을 것 같다.
태그에 비트마스킹이 있어서 비트마스킹을 이용한 DP로 푸는건줄 알았는데... (풀고나서 생각해보니 태그가 비트마스킹을 이용한 DP는 아니니까 태그의 잘못은 아니다)
비트마스킹을 왜 써야하는지는 모르겠고, 그냥 풀었다.
일단 첫번째 포인트는 스위치를 두번 누를 필요가 없다는 것이다.
이건 아마 대부분 쉽게 생각할 수 있을 것이다.
두번째 포인트는 모든 스위치를 1번 이상 누르지 않을 경우, 특정 스위치 모양을 만드는 경우의 수는 유일하다는 것이다.
이것도 쉽게 생각할 수 있다.
마지막으로 가장 중요한 포인트이자 문제 해결을 위한 핵심은, 첫번째 줄을 어떻게 키고 끌지만 결정하면 나머지 줄은 자동으로 결정할 수 있다는 것이다.
현재 위치에서의 불에 대한 판단을 switch(y,x)로 하는 것이 아니라 switch(y+1,x)로 하는것이 핵심이다. 첫번째 줄에서 경우의 수를 계산해두고, 나머지 줄에서는 현 위치가 불이 켜졌는지 꺼졌는지만 판단하고 바로 아래칸의 불을 그것에 맞춰서 켜고 꺼주면 된다.
그리고 이런 방식으로 켜고 끄면 가장 아랫줄은 확인하기도 전에 이미 결정이 나버리게 된다. 이때 가장 아랫줄이 불이 모두 꺼진 경우만이 정답으로 처리할 수 있다.
아이디어,특히 세번째 포인트를 떠올리는 것이 쉽지 않았던 문제
비트마스킹은 어떻게 활용하는지도 알아봐야겠다.
오늘의 교훈) 비트마스킹은 비트마스킹 DP만 있는게 아니다