1799. 비숍
업데이트 시간 : 2023-02-13 12:27:01 +0000[Gold I] 비숍 - 1799
성능 요약
메모리: 31256 KB, 시간: 780 ms
분류
백트래킹(backtracking)
문제 설명
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.
< 그림 1 >
그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.
< 그림 2 >
< 그림 3 >
정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.
출력
첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.
💡 Solutions
📄 비숍.py
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * (N * 3) for _ in range(2)]
def recur(row, col, cnt):
global ans
if N % 2: # 짝수일때
if col == N:
row += 1
col = 0
elif col == N + 1:
row += 1
col = 1
else: # 홀수일때
if col == N:
row += 1
col = 1
elif col == N + 1:
row += 1
col = 0
if row == N:
if ans < cnt:
ans = cnt
return
# 해당 위치에 비숍을 놓을 수 있고 오른쪽대각선은 열과 행의 합이 다똑같기 때문에 row + col
# 왼쪽대각선은 열과 행의 차(row - col)가 똑같다. 즉, 방문처리를 다음과 같이 한번에 해준다.
if arr[row][col] == 1 and not visited[0][row + col] and not visited[1][row - col]:
visited[0][row + col] = True
visited[1][row - col] = True
recur(row, col + 2, cnt + 1)
visited[0][row + col] = False
visited[1][row - col] = False
recur(row, col + 2, cnt)
ans = 0
recur(0, 0, 0)
Bcnt = ans # 검은색인 경우
ans = 0
recur(0, 1, 0)
Wcnt = ans # 흰색인 경우
print(Bcnt + Wcnt)