[Python] 1799번 비숍 (추후 보강 예정)

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

---

 

25/08/07

 

 

일단 이 문제는 여러 가지 풀이 방법이 있는데, 내가 푼 방법만 소개하도록 하겠다.

---

 

문제 접근 방식:

 

 

먼저 체스를 생각해보면, 흰색 칸의 비숍은 검은 색 칸의 비숍에 전혀 영향을 미치지 못한다.

 

반대도 마찬가지다.

 

따라서, 보드 판을 흰색 칸과 검은색 칸으로 분리할 수 있다.

 

 

이후에, 비숍은 항상 "대각선"으로 움직이므로, 보드를 45도로 돌려서 모서리 부분을 패딩한다면 비숍 문제를 룩 문제로 바꿔서 생각할 수 있다.

 

 

그리고 룩 문제에서 서로가 공격할 수 없도록 최대한의 룩을 놓으려면 각 열과 각 행에 하나씩의 룩만 놓을 수 있다.

 

N-Queen문제를 풀어봤다면 알 수 있듯, 각 열과 각 행에 하나씩의 기물을 놓는 것은 하나의 순열로 표현할 수 있다.

 

따라서 분리한 두 보드에 대해서 파이썬 itertools의 permutations함수를 사용하여 해당 위치에 놓을 수 있다면 +1을 하는 식으로 모든 경우에 대해서 구할 수 있다.

 

그리고 이는 최대 $10! * 2$가지의 경우의 수이므로(보드 2개) 시간 내에 충분히 돌아간다.

 

해당 풀이에서 가장 어려운 점은 보드를 45도 돌리고 패딩하는 부분일 것이다.

 

 

이렇게 하지 않아도 이분매칭 혹은 비트마스킹 DP로도 풀 수 있다고 하는데, 해당 풀이로는 풀어보지 않아서 추후에 작성하도록 하겠다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1799번 비숍
# 백트래킹
'''
접근 방법:
일단 흰 칸/검은 칸을 분리해서 생각해도 된다.(어차피 서로는 공격 못함)
각 보드의 최대 값을 더해서 생각하자.
45도로 보드를 돌려서 생각하자.
그러면 룩을 배치하는 것과 동일
그러면 permutationㄱㄱ
permutation 굳
'''
import sys
input = sys.stdin.readline
from itertools import permutations

N = int(input())
MAP = [list(map(int, input().split())) for _ in range(N)]
black = [[0 for _ in range(N)] for _ in range(N)]
white = [[0 for _ in range(N)] for _ in range(N)]
for s in range(0, 2*N-1, 2): # s = i+j
    row_num = s//2
    for k in range(s+1):
        r, c = s-k, k
        if r >= N or c >= N: continue
        if MAP[r][c]:
            black[row_num][k+(N-1)//2-row_num] = 1
for s in range(1, 2*N-1, 2): # s = i+j
    row_num = s//2
    for k in range(s+1):
        r, c = s-k, k
        if r >= N or c >= N: continue
        if MAP[r][c]:
            white[row_num][k+(N-1)//2-row_num] = 1

black_max = 0
white_max = 0
for tpl in permutations(range(N), N):
    black_cnt, white_cnt = 0, 0
    for i in range(N):
        if black[i][tpl[i]]:
            black_cnt += 1
        if white[i][tpl[i]]:
            white_cnt += 1
    black_max = max(black_cnt, black_max)
    white_max = max(white_cnt, white_max)

print(black_max+white_max)