아주 까다로운 문제였다.
처음에는 모든 좌표를 돌면서 비숍을 놓고, 놓은 위치의 대각선 부분을 체크하는 식으로 브루트 포스 알고리즘으로 풀려고 했다.
코드는 다음과 같다.
import sys
input = sys.stdin.readline
N = int(input())
board = []
for i in range(N):
board.append(list(map(int,input().split())))
empty = 0
for i in board:
empty += sum(i)
def check(y,x):
cant = set()
sum,dif = y+x,y-x
for i in range(N):
if N>-i+sum>=0:
if board[-i+sum][i] == 1:
cant.add((-i+sum,i))
if N>i+dif>=0:
if board[i+dif][i] == 1:
cant.add((i+dif,i))
return cant
result = 0
def bishop(y,x,cnt):
global result,empty
if result == N*2-2:
return
if cnt+empty <= result:
return
if x==N:
bishop(y+1,0,cnt)
return
if y==N:
result = max(cnt,result)
return
if board[y][x] != 1:
bishop(y,x+1,cnt)
return
cant = check(y,x)
for y1,x1 in cant:
board[y1][x1] = 2
empty -= 1
bishop(y,x+1,cnt+1)
for y1,x1 in cant:
board[y1][x1] = 1
empty += 1
bishop(y,x+1,cnt)
bishop(0,0,0)
print(result)
그러나 시간초과가 발생하였다. 이후에도 여러번 수정을 거쳤는데도 도저히 시간초과를 해결할 방법을 찾지 못했었다.
그래서 질문게시판을 살짝 봤다가 아주 큰 힌트를 얻었는데, 바로 검은색 칸과 흰색 칸을 분리해서 생각하라는 것이다.
취미로 종종 체스를 두는데 왜 이 생각을 못했지 했다. 체스에서 비숍은 검은색칸 비숍은 흰색칸으로 절대 갈 수 없고 그 반대도 마찬가지인 특성이 있다. 이를 활용하면 매우 빠르게 문제를 해결할 수 있다!
이 특성을 활용해서 짠 코드는 다음과 같다.
import sys
input = sys.stdin.readline
N = int(input())
board = []
for i in range(N):
board.append(list(map(int,input().split())))
blackcheck = {i:0 for i in range(-N//2,N//2+1)}
def black(n,cnt):
global blackcnt
if n == N:
blackcnt = max(blackcnt,cnt)
return
cant = True
for i in range(-N//2,N//2+1):
if N>n+i>=0 and N>n-i>=0:
if blackcheck[i]:
continue
if board[n+i][n-i]==1:
cant = False
blackcheck[i] = 1
black(n+1,cnt+1)
blackcheck[i] = 0
if cant:
black(n+1,cnt)
whitecheck = {i:0 for i in range(-N//2,N//2)}
def white(n,cnt):
global whitecnt
if n == N-1:
whitecnt = max(whitecnt,cnt)
return
cant = True
for i in range(-N//2,N//2):
if N>n+i+1>=0 and N>n-i>=0:
if whitecheck[i]:
continue
if board[n+i+1][n-i]==1:
cant = False
whitecheck[i] = 1
white(n+1,cnt+1)
whitecheck[i] = 0
if cant:
white(n+1,cnt)
blackcnt = whitecnt = 0
black(0,0)
white(0,0)
print(blackcnt+whitecnt)알고리즘을 요약하면
1. 칸을 흑색, 백색일때로 나눈다.
2. 흑색인 경우 (n,n), 백색일 경우 (n+1,n)을 기준으로 (제일 가운데 대각선그래프라고 생각하면 된다) 칸을 구분한다.
3. 기준칸에 대해서 좌,우 대각선 방향으로 번호를 부여하고 해당 번호에 비숍을 놓으면 그 위치에는 비숍을 놓을 수 없는 식으로 브루트 포스를 진행한다.
쉽게 말하면 비숍을 비숍이라고 생각하는게 아니고, 룩처럼 생각하고 문제를 풀면 된다. 흑색칸, 백색칸으로 구분하고 보드를 45도 회전한다고 상상해보자. 그럼 비숍이 대각선이 아닌 가로, 세로로 움직인다고 볼 수 있다. 이렇게 되면 사실상 N-Queen 문제보다 더 쉬워지는 것이다! (N-Queen과는 달리 대각선을 고려하지 않으므로)
해당 방법으로 문제를 풀자 무려 56ms만에 통과가 되었다. 다른 사람들 풀이를 보니 내 풀이가 파이썬 중에서 엄청나게 빠른 편인것 같았다.
오늘의 교훈) 때론 겹치지 않는 경우를 따로 푸는것도 필요하다