[Python/파이썬] 백준 1799번 비숍

1799번: 비숍

 

코드

import sys
input = sys.stdin.readline

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
ans = 0

rb_diag = {k: 0 for k in range(-n+1, n)}


def check_possible(diag):   # 앞으로 몇 개 더 놓을 수 있는지?
    res = 0
    for d in range(diag, 2*n-1):
        for x in range(d+1):
            y = d-x
            if 0 <= x < n and 0 <= y < n and board[x][y] and rb_diag[x-y] == 0:
                res += 1
                break
    return res


def bt(lb_diag, bishops):   # 백트래킹
    global ans
    if lb_diag == n*2-1:
        ans = max(ans, bishops)
        return
    possible = check_possible(lb_diag)
    # 앞으로 가능한 개수를 모두 놓아도 현재 ans보다 적을 때 return
    if possible+bishops <= ans: 
        return
    for x in range(lb_diag+1):  # 현재 대각선에서 놓을 수 있는 칸들
        y = lb_diag-x
        if 0 <= x < n and 0 <= y < n and board[x][y] and rb_diag[x-y] == 0:
            rb_diag[x-y] = 1
            bt(lb_diag+1, bishops+1)
            rb_diag[x-y] = 0
    bt(lb_diag+1, bishops)


bt(0, 0)
print(ans)

 

비숍은 대각선으로만 이동할 수 있다. 그렇기 때문에 같은 대각선의 좌표들이 갖는 특성을 이용하면 풀 수 있다.

왼쪽 위에서 오른쪽 아래로 내려오는 대각선에 있는 칸들은 좌표가 (x, y)일 때 x-y 값이 모두 같다. 그리고 오른쪽 위에서 왼쪽 아래로 내려오는 대각선은 x+y 값이 같다.

오른쪽 아래로 내려가는 대각선에 이미 비숍을 놓았는지 알기 위해 x-y 값을 key로 하는 딕셔너리를 만들어서 이미 놓았다면 value에 1을, 아직 놓지 않았다면 0을 저장한다.

 

그리고 아래의 함수들을 이용하여 왼쪽 아래로 내려가는 대각선을 하나씩 살펴보며 최대로 놓을 수 있는 비숍의 개수를 찾는다.

• check_possible(diag) : 현재 diag에서부터 남은 diag들에 최대 몇 개의 비숍을 놓을 수 있는지 구하는 함수. 
• bt(lb_diag, bishops)
  • 왼쪽 아래로 내려가는 대각선을 하나씩 살펴보며 비숍을 놓을 수 있는 칸에는 비숍을 놓거나 놓지 않거나 두 가지 경우로 나누어 재귀적으로 함수를 호출한다.
  • 매번 함수가 실행될 때마다 check_possible() 함수를 실행하여 현재까지 놓은 비숍의 수 bishops와 check_possible()의 리턴값을 더한 결과가 현재 최대 값인 ans보다 작다면 남은 대각선에 가능한 모든 경우를 놓아도 최대가 될 수 없다는 뜻이므로 리턴한다.
  • 아직 최대로 놓을 가능성이 있는 경우라면, 현재 대각선인 lb_diag에서 놓을 수 있는 칸을 찾는다. 현재 대각선에 속하는 칸들은 x+y = lb_diag라는 점을 이용하여 어떤 칸에 비숍을 놓을 수 있는지 구하고, 놓을 수 있는 경우에는 현재 칸이 속한 오른쪽 아래로 내려가는 대각선을 표시하기 위해 rb_diag[x-y] 값을 1로 바꿔주고 bt(lb_diag+1, bishops+1)을 재귀호출한다.
  • 현재 대각선에 놓지 않는 경우는 bt(lb_diag+1, bishops)를 재귀호출한다.