2580번 스도쿠, 백트래킹과 프랙탈 구조의 만남: AI와의 심층 탐구

백준 2580번 스도쿠 문제를 풀면서, 백트래킹 알고리즘의 원리와 프랙탈 구조를 연상시키는 탐색 트리에 대해 이해하는 시간을 가졌습니다. 처음에는 단순한 재귀로 접근하려 했지만....

학습 주제

• 오늘 공부한 주제: 백준 2580번 스도쿠 문제 해결을 위한 백트래킹 알고리즘 깊이 이해
• 대화 제목: "2580번 스도쿠 문제 백트래킹 프랙탈 구조 연상"
• 학습 날짜: 2026년 2월 4일

질문과 탐구

처음에는 스도쿠를 푸는 인간적인 접근 방식, 즉 '확정 가능한 수만 채워나가고, 여러 후보가 있을 경우 잠시 스킵하는' 로직으로 문제를 해결하려 했습니다. 하지만 이러한 방식이 AI에게 컴퓨터로 풀기에는 "반드시 막힌다"는 핵심적인 지적을 당했습니다.

이 궁금증은 다음과 같은 질문들로 이어졌습니다.

• 왜 단순히 확정 가능한 수만 채우는 방식으로는 모든 스도쿠를 풀 수 없는가?
• 인간은 어떻게 '가정'을 통해 답을 찾아나가는가? (이것이 백트래킹인가?)
• 내 아이디어의 어떤 부분을 수정해야 완전한 스도쿠 솔버가 될 수 있을까?
• 후보가 0개인 경우가 발생하는 이유는 무엇이며, 이는 무엇을 의미하는가?
• 재귀 호출 시 왜 항상 첫 빈칸부터 다시 탐색해야 하는가?
• possible 배열은 어떻게 후보들을 기억하고 처리하는가?
• solve 함수의 bool 반환값과 전역 board 배열은 어떻게 함께 작동하는가?

이 질문들을 따라가며 AI와 함께 스도쿠 문제 해결의 본질을 탐구했습니다.

핵심 학습 내용

AI와의 대화를 통해 스도쿠 문제 해결 알고리즘의 핵심은 결국 "DFS + 백트래킹 + 유효성 검사" 임을 명확히 이해했습니다.

• 제약 전파 (Constraint Propagation) vs 백트래킹 (Backtracking):

  • 처음 제안했던 "가능한 숫자가 딱 1개일 때만 확정"하는 방식은 제약 전파에 해당합니다. 이는 탐색 공간을 줄이는 데는 유용하지만, 모든 스도쿠를 풀기에는 불완전합니다.
  • 진정한 해결은 **"모르면 가정하고, 틀리면 되돌아간다"**는 백트래킹(DFS)을 통해 이루어집니다.

• 완전체 알고리즘 구조:

  1. 빈 칸을 찾습니다.
  2. 해당 칸의 가로, 세로, 3x3 격자를 검사하여 가능한 후보 집합을 계산합니다.
  3. 후보가 0개면, 이전 선택이 모순임을 의미하므로 실패를 반환합니다 (false).
  4. 후보가 1개면, 그 값을 넣고 재귀 호출을 계속합니다.
  5. 후보가 여러 개면, 하나씩 시도하고 재귀 호출합니다. 만약 실패하면 원상 복구하고 다음 후보를 시도합니다.

• possible 함수와 solve 함수의 역할:

  • possible(board, r, c, x): 현재 보드 상태에서 (r, c) 위치에 x를 넣는 것이 당장 규칙 위반인지 (가로, 세로, 격자 내 중복) 검사합니다. 이는 지역 규칙 검사기입니다.
  • solve(): 백트래킹을 통해 전체 보드가 완성될 수 있는 세계선을 탐색합니다. false는 현재 세계선이 모순임을, true는 성공적인 세계선을 발견했음을 의미하며, 이는 최종적으로 전역 board 상태를 완성합니다.

• 전역 board 배열의 중요성:

  • C/C++에서 전역 배열은 복사되지 않고 함수 간에 공유됩니다. solve 함수 내에서 board[i][j] = x 와 같이 값을 변경하면, 이는 실제 보드 상태를 직접 수정하는 것입니다. solve()가 true를 반환할 때, 이 수정된 상태가 최종 정답이 됩니다. false가 반환되면 board[i][j] = 0으로 되돌려(백트래킹) 이전 상태로 복구합니다.

• 프랙탈 구조 연상:

  • 각 빈칸에서의 선택은 새로운 분기를 만들고, 이 선택은 주변 칸들의 후보 수를 제약합니다.
  • 이러한 제약으로 인해 특정 분기는 빠르게 false를 반환하며 잘려나가고, 살아남은 세계선만이 깊이 탐색됩니다.
  • 이 과정이 반복되면서 마치 프랙탈처럼 자기유사적인 트리가 형성되며, 최종적으로 하나의 성공 경로만 남게 됩니다.

이해한 내용

이번 학습을 통해 저는 스도쿠 문제를 단순히 '숫자 채우기'가 아닌, '상태 공간 탐색(State Space Search)' 문제로 바라보는 관점을 얻게 되었습니다.

• 새로 알게 된 것:

  • 백트래킹이 '가정'과 '되돌림'을 통해 어떻게 탐색 공간을 효율적으로 줄이는지.
  • solve() 함수가 보드를 직접 수정하고, bool 반환값으로 성공/실패 신호를 전달하는 방식.
  • possible() 함수는 지역 규칙 검사, solve() 함수는 전역 세계선 탐색이라는 역할 분담.
  • 스도쿠 탐색 트리가 제약이 걸린 프랙탈 구조를 가진다는 통찰.

• 이전에 몰랐던 것과 연결:

  • 이전에는 재귀 함수가 값을 '반환'하여 다음 단계로 전달하는 방식만 생각했습니다. 하지만 solve() 함수의 bool 반환값은 데이터 반환이 아닌, **"이 세계선은 살아남았다/죽었다"**는 신호임을 이해했습니다.
  • 전역 변수나 포인터를 통해 함수 간에 동일한 데이터를 직접 수정하고 복구하는 메커니즘이 백트래킹에서 얼마나 효율적이고 필수적인지 알게 되었습니다.

• 개념 정리:

  • 제약 전파: 현재 정보로 확정 가능한 것만 푸는 방식.
  • 백트래킹: 모르면 가정하고, 틀리면 되돌아가 다른 선택을 시도하는 탐색 기법.
  • 상태 공간 탐색: 문제의 가능한 모든 상태를 탐색하여 해를 찾는 과정.
  • 세계선: 백트래킹에서 하나의 가능한 수열로 만들어진 보드 상태.
  • 모순: 특정 세계선이 더 이상 유효한 해로 진행될 수 없는 상태 (예: 후보 0개).

이번 학습은 단순한 코딩 문제를 넘어, 문제 해결의 사고방식을 이해하는 시간이었습니다. AI와의 대화를 통해 복잡하게만 느껴졌던 백트래킹의 세계가 점차 명확해지는 경험을 했습니다.