사용자 도구

사이트 도구


ps:problems:boj:9663

N-Queen

ps
링크acmicpc.net/…
출처BOJ
문제 번호9663
문제명N-Queen
레벨골드 5
분류

백트래킹

시간복잡도O(n!)
인풋사이즈n<=15
사용한 언어Python
제출기록15468ms
최고기록52ms
해결날짜2020/12/09
  • 전형적인 N-queen 문제
  • 최대 입력 사이즈가 15인데, 기본적인 백트래킹 구현만으로는 Python3의 시간제한을 맞추기 어렵다. 대칭을 이용한 속도 향상 테크닉이 들어가야만 통과 가능
  • 그렇지만, 그냥 15까지의 모든 입력에 대한 답을 미리 구해놓고 그것을 그냥 출력해주는 꼼수로 52ms에 통과하는 것도 가능하다.

풀이

코드

코드 1 - backtracking

  • 29076KB / 27556ms

"""Solution code for "BOJ 9663. N-Queen".

- Problem link: https://www.acmicpc.net/problem/9663
- Solution link: http://www.teferi.net/ps/problems/boj/9663
"""


def solve(N, first_col):
    is_occupied_col = [i == first_col for i in range(N)]
    is_occupied_up_diag = [i == first_col for i in range(N * 2 - 1)]
    is_occupied_down_diag = [i == -first_col + N - 1 for i in range(N * 2 - 1)]

    def solve_rec(row):
        if row == N:
            return 1
        count = 0
        for col in range(N):
            u_diag = row + col
            d_diag = row - col + N - 1
            if (is_occupied_col[col]
                or is_occupied_up_diag[u_diag]
                or is_occupied_down_diag[d_diag]):
                continue
            is_occupied_col[col] = True
            is_occupied_up_diag[u_diag] = True
            is_occupied_down_diag[d_diag] = True
            count += solve_rec(row + 1)
            is_occupied_col[col] = False
            is_occupied_up_diag[u_diag] = False
            is_occupied_down_diag[d_diag] = False
        return count

    return solve_rec(1)


def main():
    N = int(input())
    answer = 0
    for i in range(N // 2):
        answer += solve(N, i) * 2
    if N % 2:
        answer += solve(N, N // 2)
    print(answer)


if __name__ == '__main__':
    main()

코드 2 - backtracking on permutation

  • 29076KB / 15468ms

"""Solution code for "BOJ 9663. N-Queen".

Backtracking on permutation.
- Problem link: https://www.acmicpc.net/problem/9663
- Solution link: http://www.teferi.net/ps/problems/boj/9663
"""


def solve(N, first_col):
    cols = list(range(N))
    cols[0], cols[first_col] = cols[first_col], cols[0]
    is_occupied_up_diag = [i == first_col for i in range(N * 2 - 1)]
    is_occupied_down_diag = [i == -first_col + N - 1 for i in range(N * 2 - 1)]

    def solve_rec(row):
        if row == N:
            return 1
        count = 0
        for i in range(row, N):
            col = cols[i]
            u_diag = row + col
            d_diag = row - col + N - 1
            if is_occupied_up_diag[u_diag] or is_occupied_down_diag[d_diag]:
                continue            
            cols[row], cols[i] = cols[i], cols[row]
            is_occupied_up_diag[u_diag] = True
            is_occupied_down_diag[d_diag] = True
            count += solve_rec(row + 1)
            cols[row], cols[i] = cols[i], cols[row]
            is_occupied_up_diag[u_diag] = False
            is_occupied_down_diag[d_diag] = False
        return count

    return solve_rec(1)


def main():
    N = int(input())
    answer = 0
    for i in range(N // 2):
        answer += solve(N, i) * 2
    if N % 2:
        answer += solve(N, N // 2)
    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L G C I᠎ F
 
ps/problems/boj/9663.txt · 마지막으로 수정됨: 2020/12/09 04:52 저자 teferi