레슨 1 · 파이썬 알고리즘 골드
백트래킹은 해를 찾는 도중 막히면 이전 단계로 돌아가 다른 경로를 탐색하는 알고리즘이에요. DFS 기반으로 구현하며, 불필요한 탐색을 **가지치기(Pruning)**로 줄입니다.
탐색 시작
├─ 선택 1 → 조건 만족 → 다음 탐색
│ 조건 불만족 → 가지치기 (prune)
├─ 선택 2 → ...
└─ ...
s = [] # 현재 선택 스택
def backtrack(start):
if len(s) == M: # 종료 조건 (M개를 선택했을 때)
print(' '.join(map(str, s)))
return
for i in range(start, N + 1):
# 가지치기 조건
if 조건을_만족하지_않으면:
continue
s.append(i) # 선택 (push)
backtrack(i + 1) # 다음 단계 탐색
s.pop() # 선택 취소 (pop, 백트래킹)1~N 중에서 M개를 중복 없이 오름차순으로 선택
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N, M = map(int, input().split())
s = []
def backtrack(start):
if len(s) == M:
print(' '.join(map(str, s)))
return
for i in range(start, N + 1):
s.append(i)
backtrack(i + 1)
s.pop()
backtrack(1)8×8 체스판에 퀸 N개를 서로 공격하지 않도록 배치
N = int(input())
col = [0] * N # col[i] = i행에 놓인 퀸의 열 번호
count = 0
def is_valid(row):
for r in range(row):
if col[r] == col[row]: # 같은 열
return False
if abs(col[r] - col[row]) == abs(r - row): # 대각선
return False
return True
def backtrack(row):
global count
if row == N:
count += 1
return
for c in range(N):
col[row] = c
if is_valid(row):
backtrack(row + 1)
backtrack(0)
print(count)