[python] 백준 1799 비숍

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

1799번: 비숍

 

 

문제 해결

• 비숍을 하나 자리에 놓을 때 우상향 대각선, 우하향 대각선 두가지 위치에 비숍이 있는지 없는지 확인해야한다.
• 우상향 대각선을 두고 자리를 위치시켜가며 배열 시킬 때 우하향 대각선 어디에 비숍이 있는지는 중요하지 않다. 다만 있는지 없는지가 중요하다.
• dictionary를 통해 몇 번째 우하향 곡선에 비숍의 유무(0,1)로 확인하므로 둘 수 있는지 없는지를 확인한다.

 

 

CODE

import sys
input = sys.stdin.readline
in_range = lambda y,x: 0<=y<n and 0<=x<n

def upper_bound(diag):
    able_rus = 0

    for d in range(diag,2*n-1):
        for y in range(d+1):
            x = d-y
            if in_range(y,x) and graph[y][x] and diff[x-y] ==0: #우하향곡선에 비숍이 없을 때 놓을 수 있다.
                able_rus += 1
                break
    return able_rus 
def BackTracking(diag, cnt): # x+y=diag, cnt= diag선까지 봤을 때 비숍의 개수
    global answer
    if diag == 2*n-1: # 더이상 확인 할 것이 없을 때 (n-1,n-1)이 마지막이므로 x+y=diag에서 diag=2*n-1부터는 볼 필요가 없다.
        answer = max(answer,cnt)
        return
    ub = upper_bound(diag)
    if ub+cnt <= answer: return
    for y  in range(diag+1):
        x = diag-y
        if in_range(y,x) and graph[y][x] and diff[x-y]==0:
            diff[x-y] = 1
            BackTracking(diag+1, cnt+1)
            diff[x-y] = 0
    BackTracking(diag+1,cnt)

if __name__=='__main__':
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(n)]
    diff = {} # 우하향곡선에 있는 갯수를 구별할 것이다.
    for i in range(-n+1,n): # -n+1<=x-y<=n-1
        diff[i] = 0
    answer = 0
    BackTracking(0,0)
    print(answer)