[정글 알고리즘] -[중]-[백준 9663] N-QueenDFS

정글 알고리즘 · 중

[백준 9663] N-Queen
DFS 백트래킹 완전 정복

cedis · 2026.03.10  |  Python · 백트래킹 · DFS

백트래킹 하면 항상 나오는 문제가 있다. N-Queen이다. 처음 봤을 때는 "체스판에 퀸 N개를 놓는다"는 말만 들었는데, 막상 어떻게 풀어야 할지 감이 안 잡혔다. 이 글은 그 감을 잡는 과정을 처음부터 하나씩 따라가는 기록이다.

🔗 문제 링크: 백준 9663번 - N-Queen
N×N 크기의 체스판에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하라.

① 퀸은 어떻게 공격하나

체스의 퀸은 가로, 세로, 대각선 방향으로 몇 칸이든 이동할 수 있다. 즉, 같은 행, 같은 열, 같은 대각선에 두 번째 퀸을 놓으면 바로 공격당한다.

(0,1)에 퀸을 놓으면

♛

🔴 공격 범위

서로 공격할 수 없으려면
✅ 같은 행 ✅ 같은 열 ✅ 같은 대각선 — 이 세 가지를 피해야 한다.

② 핵심 아이디어: 한 행에 하나씩

어차피 같은 행에 퀸이 두 개 있으면 무조건 공격이다. 그러니까 처음부터 "각 행에 퀸을 하나씩만 놓자"고 규칙을 정하면 탐색이 훨씬 단순해진다.

1

0행에 퀸 하나 놓기

0열 ~ N-1열 중 하나를 선택한다.

2

1행에 퀸 하나 놓기

이전 퀸과 충돌하지 않는 열을 고른다.

3

N-1행까지 반복

모든 행에 충돌 없이 놓으면 정답 +1.

③ 상태 저장: queen[row] = col

2차원 배열 없이 1차원 배열 하나로 체스판 전체를 표현할 수 있다. 핵심은 이 한 줄이다.

# queen[row] = col
# → row번째 행에 놓인 퀸의 열 번호가 col

queen = [1, 3, 0, 2]
# 0행→1열  1행→3열  2행→0열  3행→2열Python

1

3

0

2

row 0

row 1

row 2

row 3

queen = [1, 3, 0, 2] 의 체스판

♛

♛

♛

♛

✅ N=4 정답 중 하나

왜 1차원 배열이면 충분한가?
한 행에 퀸이 하나뿐이므로, "그 행에서 퀸이 있는 열 번호"만 저장하면 체스판 전체 상태를 알 수 있다.

④ 충돌 검사: 같은 열 & 같은 대각선

한 행에 하나씩 놓기로 했으니 같은 행 충돌은 애초에 없다. 확인할 것은 딱 두 가지다.

📌 같은 열 검사

if queen[row] == queen[i]:
    return FalsePython

두 퀸의 열 번호가 같으면 충돌이다.

📌 대각선 검사 — abs() 함수 등장

새로 등장한 함수: abs(x)
파이썬 내장 함수. 숫자의 절댓값(부호를 제거한 크기)을 반환한다.
abs(-5) → 5  abs(3) → 3

두 칸이 대각선 관계인지는 이 공식 하나로 판단한다.

abs(r1 - r2) == abs(c1 - c2)

행 차이의 절댓값 = 열 차이의 절댓값 → 대각선

대각선 O: (0,1) ↔ (2,3)

♛

♛

|0-2|=2, |1-3|=2 → 대각선❌

대각선 X: (0,1) ↔ (2,0)

♛

♛

|0-2|=2, |1-0|=1 → 대각선 아님✅

if abs(row - i) == abs(queen[row] - queen[i]):
    return FalsePython

⑤ 충돌 검사 함수 possible(row)

두 조건을 묶으면 이렇게 된다. range(row)까지만 보는 이유는, 아직 놓지 않은 행(row 이후)은 비어 있기 때문이다.

def possible(row):
    for i in range(row):          # 이미 놓인 퀸들과 비교
        if queen[row] == queen[i]:    # 같은 열
            return False
        if abs(row - i) == abs(queen[row] - queen[i]):  # 대각선
            return False
    return TruePython

⑥ 백트래킹: dfs(row)

행을 하나씩 내려가면서 퀸을 놓는 함수다. 새로 등장하는 키워드 두 가지를 짚고 가자.

새로 등장한 키워드: global
함수 안에서 바깥 변수를 수정하려면 먼저 선언해야 한다.
global count → 이 함수에서 count는 바깥 변수입니다.

새로 등장한 개념: 재귀 호출
dfs(row + 1) → 같은 함수를 인자를 바꿔서 다시 호출한다.
다음 행으로 내려가는 역할이다.

dfs(row) 시작

↓

row == N ?
모든 행 완료 → count +1, return

↓ 아니면

col 0 ~ N-1 순서대로 시도

↓

possible(row) == True ?

↓ True

dfs(row + 1) 호출

↓ 돌아오면

다음 col 시도 (백트래킹)

def dfs(row):
    global count

    if row == n:          # 모든 행에 퀸을 성공적으로 배치
        count += 1
        return

    for col in range(n):  # 현재 행에서 0~N-1 열 시도
        queen[row] = col
        if possible(row):   # 충돌이 없으면
            dfs(row + 1)    # 다음 행으로 내려감Python

⑦ N=4 탐색 과정 시각화

N=4의 경우 실제로 어떻게 탐색이 진행되는지 보자.

① queen=[2,?,?,?]

♛

② queen=[2,0,?,?]

♛

♛

③ queen=[2,0,3,?]

♛

♛

♛

④ queen=[2,0,3,1] ✅

♛

♛

♛

♛

N=4의 정답은 2개뿐이다.
[1,3,0,2]  &  [2,0,3,1]

⑧ 시간 초과 → 최적화

possible(row) 함수는 퀸을 하나 놓을 때마다 이전 행 전체를 다시 순회한다. N이 커질수록 느려지는 이유다. 해결책은 열과 대각선 사용 여부를 배열에 저장해두는 것이다.

# 사용 중인 열 / 대각선을 배열로 기록
col_used   = [False] * n              # 크기 n
diag1_used = [False] * (2*n - 1)    # / 방향 대각선
diag2_used = [False] * (2*n - 1)    # \ 방향 대각선Python

⑨ 왜 2n-1개인가 — 대각선 번호 공식

체스판의 대각선은 두 종류가 있고, 각각 고유한 번호로 구분할 수 있다.

/ 방향 대각선 (row + col)

d1 = row + col

같은 / 대각선 위의 모든 칸은 row+col 값이 같다.

N=4, row+col 값

0

1

2

3

1

2

3

4

2

3

4

5

3

4

5

6

같은 숫자 = 같은 / 대각선

값의 범위: 최소 0+0=0, 최대 (n-1)+(n-1)=2n-2 → 총 2n-1개

\ 방향 대각선 (row - col + n - 1)

d2 = row - col + (n - 1)

row-col 값이 같으면 같은 \ 대각선. 음수 방지를 위해 (n-1)을 더한다.

대각선 방향	번호 공식	값 범위 (N=4)	배열 크기
/ 방향	row + col	0 ~ 6	2n-1 = 7
\ 방향	row - col + (n-1)	0 ~ 6	2n-1 = 7

⑩ 최종 코드 한글 수도코드

N을 입력받는다
count ← 0
col_used ← [False] * N
diag1_used ← [False] * (2N - 1)
diag2_used ← [False] * (2N - 1)

함수 dfs(row):

만약 row == N 이면
# 모든 행에 퀸을 배치 완료
count ← count + 1
종료

열 col ← 0 ~ N-1 반복

d1 ← row + col # / 방향 대각선 번호
d2 ← row - col + (N-1) # \ 방향 대각선 번호

만약 col_used[col] 또는 diag1_used[d1] 또는 diag2_used[d2] 이면
# 이미 사용 중인 열/대각선 → 충돌
다음 col로 건너뜀

# 퀸 배치
col_used[col] ← True
diag1_used[d1] ← True
diag2_used[d2] ← True

dfs(row + 1) # 다음 행으로 내려감

# 백트래킹: 사용 표시 복구
col_used[col] ← False
diag1_used[d1] ← False
diag2_used[d2] ← False

dfs(0) 호출
count 출력

⑪ 최종 코드

n = int(input())
count = 0

# 사용 여부 배열
col_used   = [False] * n
diag1_used = [False] * (2 * n - 1)
diag2_used = [False] * (2 * n - 1)

def dfs(row):
    global count

    if row == n:         # 모든 행 완료
        count += 1
        return

    for col in range(n):
        d1 = row + col
        d2 = row - col + n - 1

        # 충돌 검사
        if col_used[col] or diag1_used[d1] or diag2_used[d2]:
            continue

        # 퀸 배치
        col_used[col]   = True
        diag1_used[d1]  = True
        diag2_used[d2]  = True

        dfs(row + 1)      # 다음 행 탐색

        # 백트래킹
        col_used[col]   = False
        diag1_used[d1]  = False
        diag2_used[d2]  = False

dfs(0)
print(count)Python

⑫ 최적화 전후 비교

항목	기본 버전	최적화 버전
충돌 검사 방식	possible() 함수로 이전 행 전체 순회	배열 인덱스 1번으로 O(1) 검사
백트래킹 복구	queen[] 덮어쓰기 (자동)	True → False 수동 복구 필요
시간 복잡도	O(N!) × O(N) 검사	O(N!) × O(1) 검사
코드 길이	짧음	약간 길어지지만 훨씬 빠름

🎯 핵심 정리

• 한 행에 하나씩 놓는다 → dfs(row) 구조
• 충돌 조건 2가지: 같은 열 / 같은 대각선
• 대각선 판별: abs(r1-r2) == abs(c1-c2)
• 최적화: 열/대각선 사용 여부를 배열에 O(1)로 저장
• 백트래킹: dfs(row+1) 호출 전후로 True/False 토글
• 대각선 배열 크기: 2n-1 (값 범위가 0 ~ 2n-2)

· · ·

# 크래프톤정글 # 백트래킹 # DFS # N-Queen # Python # 백준9663 # 알고리즘