Dancing Links (DLX)

Dancing Links(DLX)는 Algorithm X를 효율적으로 구현하기 위한 데이터 구조입니다. 이 구조는 '연결 리스트'(Linked List) 기반으로 작동하며, 특히 열과 행의 추가 및 제거 작업이 빈번한 문제에서 큰 장점을 제공합니다.

Dancing Links의 작동 원리:

Dancing Links라는 이름은 데이터 구조의 열과 행을 추가하거나 제거하는 과정이 춤을 추듯이 부드럽게 이루어진다는 데서 유래했습니다. 이 데이터 구조는 이중 연결 리스트(Doubly Linked List)로 구성됩니다.

1. 이중 연결 리스트:
   • 각 데이터 노드는 자신을 기준으로 '왼쪽', '오른쪽', '위', '아래'에 있는 다른 노드를 가리키는 포인터를 가집니다.
   • 이 구조를 통해 노드를 삽입하거나 제거하는 작업이 매우 빠르게 이루어질 수 있습니다.
2. 열의 커버와 언커버:
   • 특정 열을 커버(cover)하는 작업은 그 열과 관련된 모든 행을 목록에서 제거하는 것을 의미합니다.
   • 언커버(uncover)는 이전에 제거된 행과 열을 다시 되돌리는 작업을 의미합니다.
   • Dancing Links에서는 이 과정이 연결 리스트의 포인터만 변경하면 되므로, 매우 효율적입니다.
3. 백트래킹:
   • Algorithm X와 동일한 방식으로, DLX는 백트래킹을 통해 가능한 모든 해를 탐색합니다.
   • 특정 선택이 잘못된 경우, 열과 행을 언커버하여 이전 상태로 돌아갈 수 있습니다.
4. 데이터 노드의 구성:
   • 각 데이터 노드는 특정한 제약 조건과 선택지 간의 관계를 나타냅니다.
   • 예를 들어, 스도쿠 문제에서는 특정 셀에 특정 숫자가 들어가는 것이 하나의 데이터 노드로 표현될 수 있습니다.