100년 뒤 개발자 한승규입니다.

브루트포스와 재귀를 이용하여 n개의 원소 중에서 m개를 고르는 조합을 찾는 알고리즘이다.

def pick(cur, cur_list):
    if cur == n:
        print(*cur_list[1:])
        return

    for i in range(cur_list[-1] + 1, m + 1):
        cur_list.append(i)
        pick(cur + 1, cur_list)
        cur_list.pop(-1)

함수를 사용했고 cur가 현재 선택한 원소의 수, cur_list가 현재 선택한 원소의 배열이다.

여기서 수를 작은 수부터 차례로 넣었기 때문에 다음에 추가할 수는 cur_list[-1]보다 큰 수부터 보면 된다.

(현재 함수에서 추가할 수는 cur_list[-1]보다 1 큰 수 부터 m까지만 보면 된다는 말)

반복문을 이용하여 수를 넣어주고, 그 배열을 바탕으로 함수를 호출하고, 배열에 들어간 수를 다시 빼주고를 반복한다.

브루투포스로 분류하기는 했지만 백트래킹 알고리즘이기도 하다. (코드를 조금만 수정하면 백준 15650의 답이다.)

해당함수를 바탕으로 작성한 전체 코드이다.

함수가 현재 배열에 있는 가장 마지막 값을 기준으로 작동하기 때문에 배열에 0을 넣어주고 시작한다.

출력시에는 1번 인덱스부터 출력할 수 있도록 한다.

# m개 중에서 n개를 고르는 모든 조합을 찾는 알고리즘, 완전탐색

import sys

print('n과 m을 입력 : ', end='')
n, m = map(int, sys.stdin.readline().split())


def pick(cur, cur_list):
    if cur == n:
        print(*cur_list[1:])
        return

    for i in range(cur_list[-1] + 1, m + 1):
        cur_list.append(i)
        pick(cur + 1, cur_list)
        cur_list.pop(-1)


pick(0, [0])

백준 9663 N-Queen문제이다.

전에 올린 백준 1799 비숍 문제와 유사하지만 조금 더 쉽다.

사용하는 방법은 백트래킹이다.

가로, 세로 한 줄에는 하나의 퀸 밖에 들어가지 못하니 한 줄을 기준으로 정하고 하나씩 더해주면 된다.(물론 불가능한 경우는 백트래킹으로 걸러주어야 한다.)

여기서는 가로로 한 줄씩 더해주었다.

이 문제에서 조금 귀찮은 부분은 대각선으로 불가능한 경우를 찾아서 제거해주는 것인데, 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)

아쉽지만 pypy3로 제출할 수 있도록 하자.

백준 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)

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