백준 1799 비숍

백준 1799 비숍 문제이다.

백준 9663 N-Queen 문제와 유사하다.

만약 문제가 풀리지 않는다면 비교적 난이도가 쉬운 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)

홀수 줄의 비숍, 짝수 줄의 비숍의 최댓값을 구한 후 각각 더했고 그 과정에서 사용한 코드는 위와 동일하다.