[Baekjoon] 1799번 : 비숍

1. 문제

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

• 백트래킹 문제

// 문제
서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 
< 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 
비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. 
< 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 
이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 
< 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다.  
색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 
체스판의 크기와 체스판 각 칸에 
비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 
서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 
비숍의 최대 개수를 구하는 프로그램을 작성하시오.

// 입력
첫째 줄에 체스판의 크기가 주어진다. 
체스판의 크기는 10이하의 자연수이다. 
둘째 줄부터 아래의 예와 같이 
체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 
체스판 한 줄 단위로 한 줄씩 주어진다. 
비숍을 놓을 수 있는 곳에는 1, 
비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

// 출력
첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

// 예제 입력 1 
5
1 1 0 1 1
0 1 0 0 0
1 0 1 0 1
1 0 0 0 0
1 0 1 1 1

// 예제 출력 1 
7

2. 핵심 아이디어

• 체스판의 검정 칸과 흰 칸을 따로 생각
• n이 짝수인 경우 한 칸씩 이동되어 칸이 구분되는 것을 고려

3. Python 문제풀이

import sys
input = sys.stdin.readline

def check(idx) :
  c = idx % 2
  i, j = idx // n, idx % n
  for d in range(4) :
    x, y = i+dx[d], j+dy[d]
    while 0 <= x < n and 0 <= y < n:
      if visited[x*n+y] :
        return False
      x += dx[d]
      y += dy[d]
  return True

def dfs(idx, c, cnt) :
  if n * n - idx + 1 + cnt <= ans[c] or idx >= n * n : 
    return
  ans[c] = max(ans[c], cnt)
  x, y = idx // n, idx % n
  j = y
  for i in range(x, n) :
    while j < n :
      v = i * n + j
      if not visited[v] and chess[i][j] == 1 and check(v) :
        visited[v] = True
        dfs(v, c, cnt+1)
        visited[v] = False
      j += 2
    j = (c + 1) % 2 if i % 2 == 0 else c

n = int(input())
chess = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [1, -1, 1, -1], [1, 1, -1, -1]
visited = [False] * (n ** 2)
ans = [0, 0]

dfs(0, 0, 0)
dfs(1, 1, 0)
print(sum(ans))

4. Java 문제풀이