[BaekJoon] 9663 N-Queen

🔦 문제 링크

✍️ 나의 풀이

---

• 백트래킹 문제
• 같은 행은 어차피 하나 밖에 못두므로 검사할 필요 없음
• 아래 열은 신경쓰지 않고 위에 열과 겹치는 부분이 있는지 검사

1. col[j] == col[i]를 통해 현재 열보다 위에 있는 열의 행과 겹치는 지 검사
2. abs(col[i] - col[j]) == (i - j) (행의 차) 와 (열의 차)가 같으면 대각선에 있는 것이므로 이를 검사

🛠 나의 코드

---

## C의 알고리즘을 그대로 따라했지만 시간초과가 발생했다..

def promising(i):
    for j in range(i):
        if col[j] == col[i] or abs(col[i] - col[j]) == (i-j):
            return False
    return True

def N_queen(i):
    global result
    if i == n:
        result += 1
    else:
        for j in range(n):
            col[i] = j
            if promising(i):
                N_queen(i+1)

n = int(input())
col = [0 for _ in range(n)]
result = 0
N_queen(0)
print(result)

✍️ 다른 사람 풀이

---

• 위(나의 코드)는 c와 알고리즘이 동일하지만 시간초과가 발생한다.
• 아래 코드는 대각선의 조건식을 구하는 방법이 특이하다.

이 그림 처럼 대각선의 조건식을 설정할 수 있다..

🛠 다른 사람 코드

---

n, ans = int(input()), 0
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)

def solve(i):
    global ans
    if i == n:
        ans += 1
        return
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]):
            a[j] = b[i+j] = c[i-j+n-1] = True
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False

solve(0)
print(ans)

📝 정리

---

• 행(row) 과 열(column)에 대한 정확한 이해가 필요하다.
• 같은 대각선은 행의 차와 열의 차가 같을 때로 구분할 수 있다.

🎈 참고

---

rebas 블로그