BOJ 9663. [Gold4] N-Queen

[hojongs]

Problem link

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

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

시뮬레이션 (백트래킹, DFS)

Pseudo-code

idea를 수도 코드로 작성해본다

아래 주석 참고

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline

board = [[0 for _ in range(14)] for _ in range(14)]
n = int(readl())

def f(ri):
    # ri >= n일 경우 1 return
    # ri번째 행의 모든 칸을 순회한다
    # 가능한 칸일 경우 퀸을 배치한다. (각 케이스)
    # ri+1...n번째 행까지 퀸이 공격하는 세로, 두 대각선에 대해 모두 +1한다
    # f(ri+1)을 호출한다
    # 케이스 별 f(ri+1) 값을 합하여 return 한다.
    if ri >= n:
        return 1

    cnt = 0
    for ci in range(n):
        if board[ri][ci] != 0:
            continue

        # 퀸 배치 (ri, ci)
        # board[ri][ci] = 99
        # 열 공격
        for ri2 in range(ri+1, n):
            board[ri2][ci] += 1
        # 대각선1 공격
        i = 1
        while ri + i < n and ci + i < n:
            board[ri+i][ci+i] += 1
            i += 1
        # 대각선2 공격
        i = 1
        while ri + i < n and 0 <= ci - i:
            board[ri+i][ci-i] += 1
            i += 1

        """
        # debug
        print("next", ri+1)
        for row in board[:n]:
            for v in row[:n]:
                print(f"{v:4d}", end='')
            print()
        """

        # 하위 경우의 수 구함
        cnt += f(ri+1)

        # 공격 초기화
        # board[ri][ci] = 0
        for ri2 in range(ri+1, n):
            board[ri2][ci] -= 1
        i = 1
        while ri + i < n and ci + i < n:
            board[ri+i][ci+i] -= 1
            i += 1
        i = 1
        while ri + i < n and 0 <= ci - i:
            board[ri+i][ci-i] -= 1
            i += 1
    return cnt

print(f(0))

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

O

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

구현력: 알고리즘을 신속, 정확하게 구현했는가?

O

[hojongs]

10초 제한에 6.5초 걸리는 알고리즘이다. 어떤 알고리즘이 있을까?

[hojongs]

a = (0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596)
print(a[int(input())])

1등(96ms) 코드. 출력 결과는 14가지이고 상수이다.

---

https://velog.io/@damiano1027/BOJ-9663%EB%B2%88-N-Queen

하위 배열에 +1 할 필요가 없다. 퀸 배치 시마다 동일 행/열/대각선에 퀸이 있는지 검사하면 된다.

이 또한 보드를 위쪽으로 순회하도록 구현할 수도 있지만(O(N)이지만 3번씩 수행한다) 이전 퀸들의 위치들을 저장해두고 동일 행/열/대각선인지 검사하면 된다 (O(N))