[ 1799 ] [ recursion ] 비숍

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

1799번: 비숍

---

풀이 과정

---

1. 핵심은 격자를 흰칸 격자, 검은칸 격자로 나누어서 보아야 한다는 점
   1. 격자의 크기가 10x10을 통째로 보게 된다면 다 한번씩 둬봐야 하므로 시간초과가 걸리게 된다.
   2. 따라서, 흰 칸에 있는 비숍, 검은 칸에 있는 비숍을 따로 보면 된다. => 5x5 격자를 두번 보는 셈
2. 우선 전체 격자를 스캔하면서 비숍의 위치를 리스트에 넣어준다.
   1. 이 때, x좌표 + y좌표가 짝수라면 흰칸, x좌표 + y좌표가 홀수이면 검은칸 
   2. 비숍의 위치가 검은칸이라면 검은칸 비숍만 저장해두는 리스트에, 흰 칸이라면 흰칸 비숍만 저장해두는 리스트에 따로따로 저장해 둔다.
3. 검은칸일때, 흰칸일때 따로따로 recursion으로 비숍을 하나하나 둬보면서 시뮬레이션 한다.
   1. i번째 비숍을 둘 때, 현재 둔 비숍과 겹치는지(대각선) 확인한다. 
   2. 겹친다면 비숍을 두지 않고 i+1번째 비숍으로 넘억나다.
   3. 겹치지 않는다면 비숍을 두고 i+1번째 비숍으로 넘어가 보고, 비숍을 두지 않을수도 있으므로 두지 않고도 i+1번째 비숍으로 넘어가본다.
4. 검은칸 일때의 최대 비숍의 수, 흰칸 일때의 최대 비숍의 수를 더한 다음 출력한다.

와.. 단순하게 격자를 10x10으로만 보았는데 찾아보니 흰칸, 검은칸을 따로따로 보아야 한다고 함.. 간단하게 소스 몇줄만 바꿔주었을 뿐인데 극적으로 효율이 좋아짐. 10x10에 대해 백트래킹 하는것 보다 5x5에 대해 백트래킹 두번 하는게 훨씬 빠르다는 거에 유의하고 백트래킹을 하려고 할 때 너무 크면 쪼개서 백트래킹 해야된다는걸 배움.

---

소스 코드

---

import sys

input = lambda : sys.stdin.readline()

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

bishop = set()
white_bishop_list = [(x, y) for x in range(n) for y in range(n) if matrix[x][y] == 1 and (x+y)%2 == 0]
black_bishop_list = [(x, y) for x in range(n) for y in range(n) if matrix[x][y] == 1 and (x+y)%2 == 1]

save = [0]

def solve(bishoppos, color):
    can_bishop_list = []
    if color == 0:
        can_bishop_list = white_bishop_list
    else:
        can_bishop_list = black_bishop_list
    
    if bishoppos == len(can_bishop_list):
        save[0] = max(save[0], len(bishop))
        return

    current = can_bishop_list[bishoppos]
    can = True
    for x, y in bishop:
        if abs(x-current[0]) == abs(y-current[1]):
            can = False
            break

    if can:
        bishop.add((current[0], current[1]))
        solve(bishoppos+1, color)
        bishop.remove((current[0], current[1]))
    solve(bishoppos+1, color)

answer = 0
# white
solve(0, 0)
answer += save[0]

# black
save[0] = 0
bishop = set()
solve(0, 1)
answer += save[0]

print(answer)