Dancing Links (DLX)

Dancing Links (DLX)

이중 연결 리스트에서 노드 삭제와 복원을 O(1)에 수행하는 기법으로, Knuth가 고안한 Algorithm X를 효율적으로 구현하여 Exact Cover 문제를 해결

목적: Exact Cover 문제 해결, 백트래킹 최적화, 효율적인 삭제/복원

특징: 이중 연결 리스트, O(1) 삭제/복원, Algorithm X 구현, 스도쿠 해결

Exact Cover 문제: 주어진 집합들 중 겹치지 않으면서 전체를 덮는 부분집합 선택

Dancing Links 원리

• •삭제: x.left.right = x.right; x.right.left = x.left;
• •복원: x.left.right = x; x.right.left = x; (x의 포인터 유지)
• •삭제 순서의 역순으로 복원하면 원래 상태 복구

Algorithm X (Knuth)

자료구조: 희소 행렬을 2D 순환 이중 연결 리스트로 표현, 열 헤더 추가

시간 복잡도: 문제 의존적, 가지치기로 평균적으로 빠름

장점: 매우 효율적인 백트래킹, 깔끔한 구현, 희소 행렬 효율

단점: 구현 복잡도, Exact Cover 문제 변환 필요

적용사례: 스도쿠, N-Queens, 폴리오미노 퍼즐, 제약 충족 문제

비교: Dancing Links(O(1)삭제복원) vs 일반백트래킹(O(n)복사)

연관: 백트래킹, Exact Cover, 제약 충족, 스도쿠, Algorithm X