가로, 세로한 줄에는하나의 퀸 밖에 들어가지 못하니 한 줄을 기준으로 정하고 하나씩 더해주면 된다.(물론 불가능한 경우는 백트래킹으로 걸러주어야 한다.)
여기서는 가로로 한 줄씩 더해주었다.
이 문제에서 조금 귀찮은 부분은 대각선으로 불가능한 경우를 찾아서 제거해주는 것인데, abs(row[x]-row[i]) == abs(x - i)로 찾아주면 된다. (가로, 세로의 차이가 같다면 대각선에 있다)
최종코드는
n = int(input())
ans = 0
row = [0] * n
def is_possible(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
return False
return True
def n_queens(x):
global ans
if x == n:
ans += 1
return
else:
for i in range(n):
# [x, i]에 퀸을 놓겠다.
row[x] = i
if is_possible(x):
n_queens(x + 1)
n_queens(0)
print(ans)
만약 문제가 풀리지 않는다면 비교적 난이도가 쉬운 N-Queen(같은 백트래킹 문제)을 먼저 풀고 오기를 바란다.
처음에 풀었던 방식은 비숍의 모든 좌표들을 구해서 하나씩 넣어가며 가능여부를 판단하는 백트래킹이었다.
import sys
N = int(sys.stdin.readline())
board = []
res = 0
for i in range(N):
board.append(list(map(int, sys.stdin.readline().split())))
left_down = [[] for i in range(2 * N - 1)]
for i in range(N):
for t in range(N):
if board[i][t] == 1:
left_down[i+t].append((i, t))
def solve(cur_list, n):
if n == 2 * N - 1:
global res
res = max(res, len(cur_list))
return
for next in left_down[n]:
flag = True
for_x = N - next[0] - 1
for_y = next[1]
for x, y in cur_list:
if for_x + for_y == (N - x - 1) + y:
flag = False
break
if flag:
solve(cur_list + [next], n + 1)
solve(cur_list, n + 1)
solve([], 0)
print(res)
이렇게 하면 시간초과가 나온다. (솔직히 시간초과 나올거 알고 있었지만 귀찮아서 이것부터 해보았다, 이러면 오히려 더 오래 걸린다 반성하자)
그 다음으로 사용한 방법은
줄을 이렇게 대각선으로 나누고 각각의 줄에 비숍이 있다면 하나씩 빼오는 것이었다 (한 줄에는 하나의 비숍만 들어갈 수 있으니, 당연히 기존의 비숍들과 계산하여 백트래킹을 사용했다.)
이렇게 만들어진 코드는
import sys
N = int(sys.stdin.readline())
board = []
res = 0
for i in range(N):
board.append(list(map(int, sys.stdin.readline().split())))
left_down = [[] for i in range(2 * N - 1)]
right_down = []
for i in range(N):
for t in range(N):
if board[i][t] == 1:
left_down[i + t].append((i, t))
def solve(cur_cnt, avoid, n):
global res
if cur_cnt + (2 * N - 1 - n) < res:
return
if n == 2 * N - 1:
res = max(res, cur_cnt)
return
for next in left_down[n]:
for_x = next[0]
for_y = N - next[1] - 1
if avoid[for_x + for_y]:
avoid[for_x + for_y] = False
solve(cur_cnt + 1, avoid, n + 1)
avoid[for_x + for_y] = True
solve(cur_cnt, avoid, n + 1)
solve(0, [True] * (2 * N - 1), 0)
print(res)
이렇게만 하면 맞을 수 있을 줄 알았다.
유사한 N-Queens 문제에서는 여기까지만 하면 맞출 수 있따.
하지만 이 코드도 시간초과가 나온다.
이 문제를 맞추기 위해서는 흰색칸의 비숍과, 검은색칸의 비숍을 분리해서 최댓값을 구한 후 더해주어야 한다.
(색이 다른 칸의 비숍들은 서로 잡을 수 없기 때문)
import sys
N = int(sys.stdin.readline())
board = []
left_down = [[] for i in range(2 * N - 1)]
odd_max = 0
even_max = 0
for i in range(N):
board.append(list(map(int, sys.stdin.readline().split())))
for i in range(N):
for t in range(N):
if board[i][t] == 1:
left_down[i + t].append((i, t))
def solve(cur_cnt, avoid, n):
global odd_max, even_max
if n >= 2 * N - 1:
if n % 2 == 0:
even_max = max(even_max, cur_cnt)
else:
odd_max = max(odd_max, cur_cnt)
return
for next in left_down[n]:
for_x = next[0]
for_y = N - next[1] - 1
if avoid[for_x + for_y]:
avoid[for_x + for_y] = False
solve(cur_cnt + 1, avoid, n + 2)
avoid[for_x + for_y] = True
solve(cur_cnt, avoid, n + 2)
solve(0, [True] * (2 * N - 1), 0)
solve(0, [True] * (2 * N - 1), 1)
print(even_max + odd_max)
홀수 줄의 비숍, 짝수 줄의 비숍의 최댓값을 구한 후 각각 더했고 그 과정에서 사용한 코드는 위와 동일하다.
