백준 1799 : 비숍

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

1799번: 비숍

 

해결 방법 : DFS

• 비숍이 위치 할 수 있는 경우를 '선택적으로' 탐색한다.
  • 사실 로직상 백트레킹 기법을 사용한 것으로 봐도 무방함
• 우선, 체스판의 최대 크기는 10*10이고, 만약 board가 모두 1(활성 상태)라면, 탐색해야 하는 비숍 배치의 경우의 수는 2^100이다. 물론 추가적으로 비숍이 서로 생존할 수 있는지를 탐색해야 하지만, 일단 생각하지말자. 아무튼, 탐색 횟수를 줄이는 '조건'을 추가하는 것이 문제의 key point임을 알 수 있다.
  • 비숍이 무한정 움직일 수 있다고 해도 서로 잡을 수 없는 경우가 있다. 좌우-앞뒤로 붙어 있는 비숍쌍을 생각하면 쉽다. 특정 비숍의 위치가 (r, c)라면, r + c 가 짝수인 경우끼리만 서로 만날 수 있음을 떠올리자. (반대로 r + c가 홀수라면 홀수인 비숍끼리만 만날 수 있을 것이다.)
  • 이를 even_bishops, odd_bishops라고 정의하고, even_bishops끼리의 비숍 위치 탐색 + odd_bishops끼리의 비숍위치 탐색으로 진행한다면 최악의 경우 2^51의 조합이 생긴다. 하지만 board 위에는 비숍이 위치 할 수 없는 공간도 주어지기 때문에 이보다는 낮을 것으로 기대한다. 
• 만약 비숍을 하나씩 추가하면 탐색하다가 불가능한 조합임을 확인하면 해당 조합을 포함하는 모든 조합은 탐색하지 않도록 가지치기한다.
  • 만약 비숍 두쌍이 (r1, c1), (r2, c2)에 위치했을 때, if abs(r1-r2) = abs(c1-c2) then, 불가능임을 생각하자. 
  • 이와 같이 백트레킹 로직이 추가되면 탐색해야 하는 조합은 기하급수적으로 줄어들 것이다.

import sys
input = sys.stdin.readline

def solution(N, board):
    answer = [0, 0] # [even_bishop 최대 개수, odd_bishop 최대 개수]
    even_bishops, odd_bishops = [], []

    for r in range(N): # even_bishop, odd_bishop 각각 비숍이 위치 가능한 좌표쌍 추가
        for c in range(N):
            if board[r][c] == 1:
                if (r + c) % 2 == 0: # even
                    even_bishops.append((r, c))
                else: # odd
                    odd_bishops.append((r, c))


    def dfs(index, entries, bishops, case): # (현재 고려할 비숍 index, 현재 존재하는 비숍들, ..., even or odd)
        for i in range(index, len(bishops)): 
            flag = True # bishops[i]가 board에 세워질 수 있는지
            for e in entries: # 현재 존재하는 비숍과 공격 가능한지 탐색
                if abs(bishops[i][0] - bishops[e][0]) == abs(bishops[i][1] - bishops[e][1]):
                    flag = False
                    break
            if flag == True: # board에 등록 가능
                entries.append(i)
                dfs(i + 1, entries, bishops, case)
                entries.remove(i)

        answer[case] = max(answer[case], len(entries)) # 마지막 비숍까지 탐색한 경우들은 entries의 개수 비교


    dfs(0, [], even_bishops, 0)
    dfs(0, [], odd_bishops, 1)

    return sum(answer)


if __name__ == '__main__':
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    result = solution(N, board)
    print(result)