Baekjoon 1799. 비숍 / Python

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

문제 해결 알고리즘

이 문제를 해결하기 위한 기본적인 접근 방법은 백트래킹을 사용하는 것입니다. 비숍은 대각선 방향으로만 이동할 수 있기 때문에, 대각선의 사용 여부를 관리하며 비숍을 배치해 나가야 합니다.

1. 대각선의 구분:
   • 비숍이 공격할 수 있는 영역은 대각선입니다.
   • 체스판의 각 칸에 대해 두 개의 대각선 정보를 유지해야 합니다.
     • 주 대각선: 같은 기울기의 대각선 (슬로프가 1인 대각선)
     • 부 대각선: 기울기가 -1인 대각선 (슬로프가 -1인 대각선)
2. 백트래킹을 통한 비숍 배치:
   • 대각선의 상태를 관리하기 위해 find 딕셔너리를 사용합니다. 이 딕셔너리는 주 대각선과 부 대각선의 사용 여부를 나타냅니다.
   • 가능한 모든 대각선 인덱스는 -n+1에서 n-1까지 입니다.
   • 각 단계에서 비숍을 놓을 수 있는지 확인하고 놓은 경우, 다음 단계로 넘어갑니다.
   • 비숍을 놓지 않는 경우, 다음 단계로 넘어갑니다.
   • 가능한 모든 경우를 탐색하면서 최대 비숍의 수를 기록합니다.

import sys
input = sys.stdin.readline

# 체스판의 크기
n = int(input())

# 체스판의 각 칸이 비숍을 놓을 수 있는지 없는지 정보
# 1은 비숍을 놓을 수 있는 칸, 0은 놓을 수 없는 칸
chess = [list(map(int, input().split())) for _ in range(n)]

# 각 대각선의 상태를 저장할 딕셔너리
# 주 대각선과 부 대각선 모두 사용 여부를 저장
find = {}

# 비숍을 놓을 수 있는 대각선의 범위는 -n+1에서 n-1까지
# 딕셔너리 초기화
for i in range(n):
    find[i] = 0  # 주 대각선
    find[-i] = 0  # 부 대각선

# 비숍이 놓일 수 있는 칸을 찾는 함수
def bishop(idx):
    ans_tmp = 0  # 현재 대각선에서 비숍을 놓을 수 있는 칸의 수를 저장
    for dist in range(idx, 2 * n - 1):
        for tmp_x in range(dist + 1):
            tmp_y = dist - tmp_x
            # 체스판의 범위를 벗어나지 않으며 비숍을 놓을 수 있는 위치인지 확인
            if 0 <= tmp_x < n and 0 <= tmp_y < n and not find[tmp_x - tmp_y]:
                ans_tmp += 1  # 놓을 수 있는 칸을 찾으면 카운트
                break  # 대각선에서 첫 번째 유효한 칸을 찾았으므로 반복을 종료
    return ans_tmp  # 찾은 칸의 수를 반환

# 백트래킹을 통해 최대 비숍의 수를 찾는 함수
def bfs(idx_ = 0, cnt = 0):
    global ans  # 전역 변수로 최댓값을 저장
    if idx_ == 2 * n - 1:  # 모든 대각선을 검사했으면
        ans = max(ans, cnt)  # 현재까지의 비숍 개수 중 최댓값을 갱신
        return
    
    # 현재 대각선에서 비숍을 놓을 수 있는 칸의 수를 계산
    s_tmp = bishop(idx_)
    if s_tmp + cnt <= ans:  # 현재 상태에서 더 이상의 비숍 배치는 불필요한 경우
        return
    
    # 현재 대각선에서 비숍을 놓을 수 있는 모든 칸을 검사
    for tmp_x in range(idx_ + 1):
        tmp_y = idx_ - tmp_x
        # 체스판의 범위를 벗어나지 않으며 비숍을 놓을 수 있는 위치인지 확인
        if 0 <= tmp_x < n and 0 <= tmp_y < n and chess[tmp_x][tmp_y] and not find[tmp_y - tmp_x]:
            find[tmp_y - tmp_x] = 1  # 비숍을 놓을 수 있는 위치로 설정
            bfs(idx_ + 1, cnt + 1)  # 다음 대각선으로 넘어가며 비숍의 수를 1 증가
            find[tmp_y - tmp_x] = 0  # 원상 복구: 다음 탐색을 위해 비숍을 제거
    
    # 현재 대각선에서 비숍을 놓지 않는 경우를 탐색
    bfs(idx_ + 1, cnt)


bfs()


print(ans)