백트래킹 & N-Queen 문제 정리

 

1️⃣ 백트래킹 (Backtracking) 개념

백트래킹은 모든 경우를 탐색하면서, 불가능한 경우는 빠르게 포기(가지치기)하여 탐색량을 줄이는 기법.

 

✅ 기본 원리:

1. 가능한 모든 경우를 탐색 (완전 탐색).

2. 유효하지 않은 경우를 빨리 제거하여 탐색 시간을 줄임.

3. 탐색이 실패하면 "이전 상태"로 돌아감 (백트래킹).

 

✅ 언제 사용하나?

- N-Queen 문제, 순열/조합 문제, 수식 만들기, 미로 탐색 등에서 많이 사용됨.

- 완전 탐색은 시간이 너무 오래 걸릴 때, 가지치기를 통해 불필요한 탐색을 줄여야 할 때 사용됨.

 

---

2️⃣ N-Queen 문제 풀이 방법

 

(문제 링크)

 

✅ 문제 요약:

- NxN 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제.

- 퀸(Queen): 같은 행, 같은 열, 대각선 방향으로 공격 가능.

 

✅ 핵심 아이디어:

- 한 행(row)에 하나의 퀸만 배치하면, 수직(열) 충돌은 자동으로 해결됨.

- 즉, 한 행(row)에 대해 하나의 열(col)을 선택하는 방식으로 문제를 해결할 수 있음.

- n_queens(row) 함수에서 현재 row에 퀸을 배치하고, 다음 행(row+1)을 탐색하는 방식.

 

✅ 세로 방향 충돌을 줄이는 이유

- 한 행에 하나씩만 배치하면 같은 행에 두 개의 퀸이 존재할 수 없기 때문에 가로 충돌은 애초에 발생하지 않음.

- 따라서 고려해야 할 것은 세로(열) 충돌과 대각선 충돌만 체크하면 됨.

 

---

3️⃣ N-Queen 백트래킹 코드 (Python)

def is_valid(row):
    """현재 row에 배치한 퀸이 유효한지 검사"""
    for prev_row in range(row):
        # 1. 같은 열에 퀸이 있는 경우
        if board[prev_row] == board[row]:
            return False
        # 2. 대각선에 퀸이 있는 경우
        if abs(board[row] - board[prev_row]) == abs(row - prev_row):
            return False
    return True

def n_queens(row):
    """row 번째 행에 퀸을 배치하는 함수"""
    global count  # 전역 변수 count 사용
    if row == N:  # 모든 행에 퀸 배치 완료 (기저 조건)
        count += 1
        return

    for col in range(N):  # 가능한 열(column) 탐색
        board[row] = col  # 현재 행(row)에 col에 퀸 배치
        if is_valid(row):  # 유효한 경우만 다음 행 탐색
            n_queens(row + 1)  # 다음 행(row+1) 탐색

N = int(input())  # 체스판 크기 입력
board = [-1] * N  # 퀸이 놓인 열(column) 위치 저장
count = 0  # 가능한 배치 개수 저장 변수

n_queens(0)  # 첫 번째 행부터 탐색 시작

print(count)  # 가능한 배치 개수 출력

 

 

같은 코드인데, python3으로 하니깐 시간 초과이고, PyPy3으로 하니깐 성공.... (두 언어 무슨 차이지...)

---

4️⃣ 헷갈렸던 부분 정리

📌 실행 흐름 분석 (N=4)

1. n_queens(0) 호출

   - col = 0일 때, board = [0,-1,-1,-1]

   - is_valid(0) = True -> n_queens(1) 호출

2. n_queens(1) 호출

   - col = 0,1일 때, is_valid(1) = False (충돌)

   - col = 2일 때, board = [0,2,-1,-1]

   - is_valid(1) = True -> n_queens(2) 호출

3. n_queens(2) 호출

   - col = 0,1,2,3 모두 탐색 -> 모두 is_valid(2) = False (충돌)

   - 마지막으로 col=3 탐색한 후, board = [0,2,3,-1] 상태가 됨.

4. n_queens(2)에서 가능한 경우가 없으므로, n_queens(1)로 백트래킹

 

📌 헷갈렸던 부분

 

💡 질문: 

n_queens(2)의 마지막 board 상태는 [0,2,3,-1]인데, n_queens(1)로 돌아가면 왜 [0,2,-1,-1]로 돌아가는 걸까?

 

내가 생각했을 때는, n_queens(1)로 돌아갈 때, board[2] = 3이 남아있으니깐, n_queens(1)에서 col=3 탐색하면 board = [0,3,3,-1]이 된다고 생각하는데...

 

🔎 답변:

✅ 재귀 함수가 호출될 때마다 이전 상태가 Call Stack(호출 스택)에 저장됨.

✅ n_queens(2)가 끝나면, 저장된 n_queens(1)의 상태로 자동 복원됨.

✅ 즉, board[2] = 3 값이 유지되지 않고, 이전 board[2] = -1 상태로 돌아감.

✅ 따라서, n_queens(1)에서 다음 col=3을 탐색하면, board = [0,3,-1,-1]로 덮어씌워짐.