[백준]1799 비숍 #백트래킹

1. 풀이

(1) 시간복잡도

그냥 풀면 정말 간단한 백트래킹 문제이지만 시간이 O(2^(N*N)) 이므로 초과이다. 

해법은 체스판의 특성을 생각하고 하얀색 체스판에 채울 수 있는 최대의 비숍과 검은색 체스판에 채울 수 있는 최대의 비숍을 각각 따로구해서 더해주는 것이다.

이렇게 하면 시간복잡도는 아래와 같이 된다.

O(2^(N/2*N/2)+2^(N/2*N/2))=O(2^(N/2*N/2))

 

(2) N이 짝수일 때 주의사항

N이 홀수이면 확인할 블럭이 아래와 같이 2씩 증가하지만

0		3
	5
7		9

N이 짝수이면 확인할 블럭이 마지막 or 마지막 바로앞 열에서 3 or 1씩 증가해야 한다

0		2
	5		7
8		10
	13		15

따라서 이를 유의해서 탐색을 해줘야한다!

 

2. 소스코드

dR=[-1,-1,1,1]
dC=[-1,1,-1,1]

N=int(input())
L=[]
for i in range(N):
    L.append(list(map(int,input().split())))
maxNum=N*N

# myL에 r,c에 비숍놔둬도 되나?
def isPossible(r,c):
    if L[r][c]==0:
        return False
    for k in range(4):
        for i in range(1,N):
            tempR=r+dR[k]*i
            tempC=c+dC[k]*i
            if 0<=tempR<N and 0<=tempC<N:
                if L[tempR][tempC]==2:
                    return False
            else:
                break
    return True

def dfs(num,cnt):
    global ans
    if num>=maxNum:
        if ans<cnt:
            '''
            print()
            for i in L:
                print(i)
            '''
            ans=cnt
        return

    r=num//N
    c=num%N

    # 비숍놓는경우
    if isPossible(r,c):
        L[r][c]=2
        if N%2==0:
            if c==N-1:
                dfs(num+1,cnt+1)
            elif c==N-2:
                dfs(num+3,cnt+1)
            else:
                dfs(num + 2, cnt + 1)
        else:
            dfs(num+2,cnt+1)
        L[r][c]=1
    # 비숍 안놓는경우
    if N%2==0:
        if c == N - 1:
            dfs(num + 1, cnt)
        elif c == N - 2:
            dfs(num + 3, cnt)
        else:
            dfs(num + 2, cnt)
    else:
        dfs(num+2,cnt)


ans=0
dfs(0,0)
ansWhite=ans

ans=0
dfs(1,0)
ansBlack=ans

print(ansWhite+ansBlack)