인공지능(AI) 알고리즘을 공부하다 보면 스도쿠, 십자말풀이, 스케줄링 같은 문제들을 마주하게 됩니다. 이를 제약 만족 문제(CSP, Constraint Satisfaction Problem)라고 부릅니다. 이런 문제를 풀 때 가장 직관적인 접근은 '백트래킹(Backtracking)'입니다. 하지만 무작정 값을 찔러보고 아니면 되돌아오는 방식은 경우의 수가 조금만 늘어나도 연산 시간이 우주를 뚫고 나갑니다.

이때 탐색 공간을 극적으로 압축하여 백트래킹 엔진에 날개를 달아주는 전처리 알고리즘이 있습니다. 바로 AC-3 (Arc Consistency 3) 알고리즘입니다. 오늘은 이 알고리즘이 어떻게 불가능한 오답들을 미리 가지치기하는지, 그 직관적인 원리를 파헤쳐 보겠습니다.

1. CSP의 3대 핵심 용어

알고리즘을 이해하기 위해 먼저 우리가 다룰 데이터를 정의해 보겠습니다.
  • 노드(Node): 값을 할당해야 할 변수 (예: 십자말풀이의 빈칸 X, Y)
  • 도메인(Domain): 각 변수에 들어갈 수 있는 후보 값들의 집합 (Dx, Dy)
  • 아크(Arc): 두 변수 사이의 제약 조건 (방향성을 가진 간선 X → Y)
여기서 가장 헷갈리기 쉬운 개념이 바로 아크(Arc)입니다. "단순히 두 빈칸이 겹친다는 뜻 아닌가? 왜 하필 화살표(→)로 방향성을 표현할까?"라는 의문이 들 수 있습니다.

2. 아크(X → Y)의 진짜 의미: 단방향 필터링

아크를 단순한 연결선이 아니라, '단방향 검증 명령서'라고 생각해 보세요. X → Y라는 아크는 다음과 같은 철저한 역할 분담을 의미합니다.
  • 도착점 Y (심사위원): 평가의 기준이 됩니다. Y의 도메인(단어장)은 절대 깎이지 않습니다.
  • 출발점 X (참가자): 필터링을 당하는 대상입니다. Y의 기준에 맞지 않는 후보 단어들은 가차 없이 삭제됩니다.

이를 코드로 구현한 것이 바로 revise(X, Y) 함수입니다.

"심사위원 Y의 도메인에 있는 어떤 단어와도 교차점 스펠링이 맞지 않는 X의 단어들을 모두 지워라!"라는 뜻이죠. 방향성이 반대인 Y → X 라면, 반대로 X가 심사위원이 되어 Y를 평가합니다.

3. AC-3 알고리즘: 상태 전파의 예술

단순히 모든 변수 쌍을 한 번씩 비교하고 끝난다면, 그것은 완벽한 알고리즘이 아닙니다. 퍼즐 한쪽에서 일어난 변화는 연쇄적으로 다른 쪽의 일관성을 깨뜨릴 수 있기 때문입니다. AC-3는 큐(Queue)를 활용하여 이 '나비효과'를 네트워크 전체로 전파시킵니다.

- AC-3 파이썬 수도코드

def ac3(csp):
    # 1. 모든 아크(교차점 쌍)를 큐에 넣고 시작
    queue = [(X, Y) for X in csp.variables for Y in csp.neighbors(X)]
    
    while queue:
        X, Y = queue.pop(0)
        
        # 2. Y를 심사위원으로 삼아 X의 도메인을 다이어트!
        if revise(csp, X, Y):
            if len(csp.domains[X]) == 0:
                return False # 남은 후보가 없으면 퍼즐 실패
            
            # 3. 나비효과: X의 상태가 변했으니, X를 믿고 있던 이웃 Z들을 다시 큐에 넣음
            for Z in csp.neighbors(X) - {Y}:
                queue.append((Z, X))
                
    return True

4. 왜 집합 연산 - {Y}를 할까?

위 코드에서 가장 소름 돋는 최적화 포인트는 바로 큐에 이웃들을 다시 넣을 때 원인 제공자인 Y를 빼버리는(- {Y}) 부분입니다. 왜 뺄까요?
  • Z를 큐에 넣는 이유 (Z, X): 방금 X의 도메인에서 단어들이 삭제되었습니다. 그래프 반대편에 있는 이웃 Z의 단어장에는, 방금 삭제된 X의 단어만을 유일한 짝꿍으로 믿고 있던 데이터가 있을 수 있습니다. 짝꿍이 사라졌으니 그 데이터는 이제 쓸모없는 '좀비 데이터'입니다. 따라서 X를 새로운 심사위원으로 모시고 Z를 재검증해야 합니다.
  • Y를 빼는 이유 - {Y}: 방금 X에서 값들이 삭제된 이유는 오로지 "Y의 기준에 맞지 않아서"입니다. 즉, 현재 X에 살아남은 알맹이들은 애초에 Y와 100% 호환됨이 보장된 정예 멤버들입니다. 따라서 굳이 Y를 다시 큐에 넣어서 Y와 X를 또 검사하는 무의미한 연산(무한 루프)을 할 필요가 없는 것입니다.

 

 

특정 노드의 상태 변화를 추적하고,
의존성이 있는 인접 노드에게만 그 변화를 선택적으로 전파한다.

 

AC-3 알고리즘은 탐색 공간을 극단적으로 다이어트시켜 백트래킹의 성공률을 폭발적으로 높여주는 강력한 전처리 엔진입니다. 이 우아한 아키텍처는 비단 AI 탐색뿐만 아니라, 현대 프론트엔드 프레임워크의 반응형 상태 관리나 분산 시스템의 이벤트 전파 모델과도 그 결이 매우 닿아있습니다. 1970년대의 고전 알고리즘이 여전히 현대 소프트웨어 엔지니어링에 큰 영감을 주고 있습니다.

티스토리툴바