🧩패러다임
Backtracking Algorithms
Try, and step back when you hit a wall. Learn the 3 topics below step by step with interactive visualizations.
🧩N-퀸 (N-Queens)
N×N 체스판에 서로 공격하지 못하도록 N개의 퀸을 놓는 문제입니다. 한 행씩 퀸을 시도하고 열·대각선 충돌을 검사하며, 막히면 직전 선택으로 되돌아가는(backtrack) 전형적인 백트래킹입니다.
O(N!)🧩미로 탈출 (Maze Solver)
격자 미로에서 출발점부터 도착점까지의 경로를 찾는 문제입니다. 한 방향으로 나아가다 벽이나 막다른 길을 만나면 마지막 갈림길로 되돌아가며 다른 방향을 시도하는 백트래킹으로 해결합니다.
O(4^(N·M))🧩스도쿠 (Sudoku Solver)
9×9 격자에 행·열·3×3 박스마다 1~9가 한 번씩만 오도록 채우는 퍼즐입니다. 빈 칸에 가능한 숫자를 하나씩 시도하고, 모순이 생기면 0으로 되돌려 다른 숫자를 시도하는 백트래킹입니다.
O(9^(빈 칸))