[백준 1799번] 비숍(파이썬)

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

1799번: 비숍

이 문제는 백트레킹 문제중에서

난이도가 상당히 높은 문제.

 

우선 제가 초기에 풀었을 때는

'정석(?)'대로

대각선이 비어있는지 확인해주고

비숍을 넣는 방식이었습니다.

import sys
sys.setrecursionlimit(10**8)
N=int(input())
room=[list(map(int,input().split())) for _ in range(N)]
ga=[False]*(2*N-1)
sa=[False]*(2*N-1)
answer=0
def dfs(x,y,bi):
    global answer

    if y==N:
        dfs(x+1,0,bi)
        return
    if x==N:
        answer=max(answer,bi)

        return

    if room[x][y]==1:
        if ga[x+y]==False and sa[x-y+N-1]==False:
            ga[x+y]=True
            sa[x-y+N-1]=True

            dfs(x,y+1,bi+1)
            ga[x+y]=False
            sa[x-y+N-1]=False
    dfs(x,y+1,bi)

    return
dfs(0,0,0)
print(answer)

이 방식은 시간초과가 바로 발생했습니다.

문제 곧이 곧대로 풀었는데

무슨 방법이 더 있나...

 

구글링해서 알아낸 힌트는

흰색,검은색을 따로 분리해서 계산하는 방법.

체스판에서는 흰색,검은색이

각각 지그제그로 표시가 되어있습니다.

비숍을 흰색 칸에 두면

비숍은 흰색 칸만 움직이고

검은색칸에 두면

검은색 칸만 움직이죠.

그래서

'흰색칸을 넣을때 최대'

'검은색칸을 넣을 떄 최대'

각각을 구한다음에 더해주는 방식이었죠.

N=int(input())
room=[list(map(int,input().split())) for _ in range(N)]
black=[]
white=[]
color=[[0]*N for _ in range(N)]

for x in range(N):
    for y in range(N):
        if (x+y)%2==0:
            color[x][y]=0
            if room[x][y]==1:
                black.append((x,y))
        else:
            color[x][y]=1
            if room[x][y]==1:
                white.append((x,y))

w_cnt=0
b_cnt=0
da=[False]*(2*N-1)
da_2=[False]*(2*N-1)

def put(box,index,count):
    global w_cnt,b_cnt
    if index==len(box):
        if box==white:
            w_cnt=max(w_cnt,count)

        else:
            b_cnt=max(b_cnt,count)

        return

    x,y=box[index]
    if da[x+y] or da_2[x-y+N-1]:
        put(box,index+1,count)
    else:
        da[x+y]=True
        da_2[x-y+N-1]=True
        put(box,index+1,count+1)
        da[x+y]=False
        da_2[x-y+N-1]=False
        put(box,index+1,count)


if len(white)>0:
    put(white,0,0)
if len(black)>0:
    put(black,0,0)

print(w_cnt+b_cnt)

백트레킹을 어떻게 하면

시간을 줄일 수 있을지

생각하게 만들어준 좋은 문제입니다.