문제 바로가기
문제:
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.
그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.
정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.
출력:
첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.
풀이:
이 문제는 N-Queen 문제와 유사하다.
하지만 대각선을 체크한다는 것이다. 대각선은 오른쪽 방향 대각선 왼쪽 방향 대각선 이렇게 2개다
대각선들은 짝수칸일때 홀수 칸 일때 서로 영향을 주지 않는다.
짝수칸일때 , 홀수칸일때 를 정한 후
오른쪽 방향 대각선일때, 왼쪽 방향 대각선일때 를 나눠 2개를 더해주면 퀸을 둘 수 있는 최댓값이다.
근데 퀸을 두지 않는 경우도 고려해준다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
black = []
white = []
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
# 짝수
if (i + j) % 2 == 0:
black.append((i, j))
else: # 홀수 칸
white.append((i, j))
def is_possible(x, y, right, left):
# 대각선 체크
if not right[x+y] and not left[x-y+n-1]:
return True
return False
def bt(spots, index, right, left):
if index == len(spots):
return 0
x, y = spots[index]
max_count = bt(spots, index + 1, right, left) # 비숍을 놓지 않는 경우
if is_possible(x, y, right, left): # 비숍을 놓을 수 있는 경우
right[x + y] = True
left[x - y + n - 1] = True
max_count = max(max_count, 1 + bt(spots, index + 1, right, left))
right[x + y] = False
left[x - y + n - 1] = False
return max_count
right_black = [False] * (2 * n - 1)
left_black = [False] * (2 * n - 1)
right_white = [False] * (2 * n - 1)
left_white = [False] * (2 * n - 1)
b = bt(black, 0, right_black, left_black)
w = bt(white, 0, right_white, left_white)
댓글