홈 / 소코반 솔버 알고리즘
소코반 알고리즘 가이드

소코반 솔버 알고리즘: 탐색으로 해답을 찾는 방법

소코반 솔버는 상자 밀기 퍼즐을 보드 상태 탐색으로 바꿉니다. 상자 위치, 이동 가능한 바닥, 가능한 밀기와 이미 확인한 상태를 기록합니다.

이 가이드는 솔버의 작동 방식을 설명합니다. ASCII 보드를 입력해 경로를 얻으려면 온라인 솔버 페이지를 사용하세요.

2026년 11월 16일 업데이트플레이어, 퍼즐 제작자, 프로그래머를 위한 안내

상자, 목표, 벽, 접근 칸을 보여 주는 소코반 보드

솔버는 보드를 단순한 그림이 아니라 상태 그래프로 평가합니다.

빠른 답변: 요약하면 솔버는 간결한 상태를 저장하고, 영역 채우기로 플레이어가 걸어갈 수 있는 바닥을 구한 뒤 합법적인 밀기만 생성합니다. 중복 상태와 명백한 교착 상태를 제거하고, 발견한 해를 조작 순서로 복원할 수 있도록 부모 상태 링크를 남깁니다.

소코반에서 중요한 단위는 보통 방향키 한 번이 아니라 상자 밀기입니다. 밀기 사이의 걷기는 플레이어의 위치만 바꿉니다. 따라서 보드를 그래프로 볼 수 있습니다. 노드는 알려진 상태이며, 간선은 합법적인 밀기 한 번과 다음 상자 뒤에 서는 데 필요한 걷기입니다.

밀기를 항상 되돌릴 수는 없으므로 이 그래프는 커집니다. 상자를 움직이려면 반대편에 서야 하고 잘못된 모서리에 넣은 상자를 끌어낼 수는 없습니다. 각 노드에서 어떤 바닥에 상자가 있는지, 상자를 옮기지 않고 플레이어가 어디까지 갈 수 있는지 판단할 정보를 보존해야 합니다.

모든 목표가 채워지면 부모 링크를 시작점까지 따라가 경로를 복원합니다. 방향 문자열에 걷기가 많이 포함되어도 중요한 결정은 상태를 바꾼 밀기입니다.

보드 상태를 표현하는 방법

보드에는 고정 데이터와 변하는 데이터가 있습니다. 벽과 목표는 한 번만 분석하면 됩니다. 변하는 부분은 상자 좌표 집합과 플레이어의 도달 가능 영역입니다. 상자를 통과하지 않고 오갈 수 있는 두 플레이어 위치는 보통 같은 상황입니다. 이를 정규화하면 동등한 걷기 위치가 대기열을 채우는 것을 막습니다.

상태 구성 요소기록 내용역할
벽과 목표보드의 고정 구조이동 가능한 바닥과 완료 조건을 정의합니다.
상자 배치상자별 좌표가능한 밀기와 목표 배정을 결정합니다.
플레이어 영역밀지 않고 도달할 수 있는 바닥상자의 어느 쪽에 설 수 있는지 보여 줍니다.
부모와 동작직전 상태와 밀기 방향가능 여부뿐 아니라 찾은 경로를 재현합니다.

전이표 또는 방문 집합은 정규화된 상태마다 키를 저장합니다. 동일한 상자 배치와 도달 가능 영역을 다시 탐색해도 새로운 후속 경로는 나오지 않습니다. 메모리를 사용해 속도를 얻는 방식입니다.

제약이 있는 목표와 대기 공간으로 상자 순서를 계획하는 소코반 보드

설명용 보드 그림: 상자 순서는 각 밀기 이후 도달 가능한 상태를 바꿉니다. 솔버 코드 화면이 아니라 개념을 보여 주는 그림입니다.

탐색 프런티어가 확장되는 방법

상태를 분석하면 영역 채우기로 걸어갈 수 있는 범위를 구합니다. 각 상자의 네 방향을 확인하며, 목적지가 빈 바닥이고 반대편에 설 수 있을 때만 밀기가 합법입니다. 상자를 옮긴 다음 플레이어 영역을 다시 계산하여 새 상태를 만듭니다.

탐색 순서에 따라 보장되는 성질이 다릅니다. 너비 우선 탐색은 짧은 밀기 순서부터 조사하므로 간선 비용이 같으면 최소 밀기 해를 찾습니다. 깊이 우선 탐색은 한 분기를 깊게 따라가 대기 상태 메모리를 줄이지만, 유용하지 않은 분기에 오래 머물 수 있습니다. 균일 비용 탐색이나 A*는 밀기 비용과 휴리스틱을 결합할 수 있으나, 추정의 품질과 성질이 결과의 의미를 결정합니다.

  1. 분석.벽, 목표, 상자, 플레이어를 읽고 잘못된 개수나 미지원 기호를 거부합니다.
  2. 도달 범위.상자를 옮기지 않고 갈 수 있는 바닥을 표시합니다.
  3. 확장.서는 칸과 목적지가 모두 유효한 밀기를 생성합니다.
  4. 가지치기와 기록.중복과 명백한 교착을 건너뛰고 부모 상태와 밀기를 저장합니다.
  5. 종료.모든 목표가 채워지면 멈추고, 한도 내에서 경로를 못 찾으면 그 사실을 알립니다.

각 걷기 경로를 따로 저장할 필요는 없습니다. 밀기 이후 정규화된 도달 가능 영역 하나면 다음 밀기를 생성할 수 있습니다. 덕분에 작은 브라우저 솔버도 실용적으로 동작합니다.

교착 가지치기가 중요한 이유

가지치기가 없으면 해에 도달할 수 없는 배치에 시간을 낭비합니다. 가장 쉬운 규칙은 목표가 아닌 모서리입니다. 직각으로 만나는 두 벽에 붙은 상자는 빠져나올 수 없으므로 즉시 분기를 버립니다. 맞는 목표가 없는 벽 구간, 얼어붙은 2×2 묶음, 한 칸 통로를 막는 상자도 흔히 검사하는 패턴입니다.

상자가 고정되지 않아도 접근이 막힐 수 있습니다. 올바른 목표에 놓인 상자가 다른 상자를 밀기 위한 유일한 자리를 차지할 수 있습니다. 두 상자가 움직여도 분리하는 데 필요한 쪽으로 플레이어가 갈 수 없을 수 있습니다. 이런 문제는 탐지가 어려워 단순 패턴, 중복 검사, 유한한 탐색 예산을 함께 사용합니다.

탐색 가지치기를 설명하는 소코반 모서리 교착 예시

모서리 교착은 깊게 탐색하기 전에 알아낼 수 있어 유용합니다. 더 복잡한 접근 실패는 넓은 상태 검사가 필요합니다.

가지치기는 정확성도 고려해야 합니다. 지나치게 강한 규칙은 예외적인 성공 경로까지 지울 수 있습니다. 작은 브라우저 도구는 모든 ‘해 없음’을 증명이라고 부르기보다 가지치기의 적용 범위를 설명해야 합니다.

밀기 비용, 걷기 비용, 휴리스틱

‘최단 해’는 무엇을 최소화하는지 먼저 정해야 합니다. 밀기 최적 경로는 상자 밀기를 줄이고, 이동 최적 경로는 걷기도 포함합니다. 방을 돌아서 오래 걸으면 밀기 한 번을 줄이고 상자 배정을 안전하게 유지할 수 있어 두 목표는 충돌합니다. 솔버는 우선할 비용을 정하고 결과에 그 기준을 표시해야 합니다.

휴리스틱은 완료까지 남은 거리를 추정합니다. 간단한 방식은 격자 거리로 상자와 목표를 연결하고 벽에 갇힌 상자에 벌점을 더합니다. 벽, 접근 칸, 상자 순서 때문에 실제 경로는 단순 거리보다 복잡합니다. 추정은 유망한 상태를 우선하도록 도울 뿐 정확한 거리를 증명하지는 않습니다.

작은 보드에는 이동 문자열, 밀기 수, 걷기 수, 검사한 상태 수를 표시하면 좋습니다. 독자는 최적성이 증명되지 않은 결과를 최적해로 오해하지 않고 자신의 계획과 비교할 수 있습니다.

작은 보드 탐색 예시

상자 하나인 예시입니다. #는 벽, .는 목표, $는 상자, @는 플레이어입니다.

#####
# . #
# $ #
# @ #
#####

초기 도달 가능 영역에는 플레이어 칸과 상자 아래 바닥이 있습니다. 상자 아래에 서서 위쪽 목표로 밀 수 있으므로 합법적인 밀기 하나를 찾습니다. 새 상자 좌표를 기록하고 플레이어 영역을 다시 계산하면 모든 목표가 채워졌음을 확인합니다. 부모 링크만으로 필요한 걷기와 밀기 한 번으로 된 짧은 경로를 복원할 수 있습니다.

어려운 보드의 프런티어에는 여러 밀기 후보가 있습니다. 모서리로 가는 분기는 가지치기로 사라지고 움직일 수 있는 분기는 대기열에 남습니다. 무작위 시도와 확인한 정보를 기억하는 탐색의 차이입니다.

솔버가 멈추거나 실패를 알리는 경우

브라우저 솔버는 여러 이유로 멈춥니다. 상자와 목표 수가 다르거나, 미지원 기호가 있거나, 플레이어가 없어 입력이 잘못될 수 있습니다. 유효한 보드라도 안전한 행·열·상자·방문 상태 수 한도를 넘을 수 있습니다. 또는 제한된 탐색의 후보를 모두 조사해도 해를 못 찾을 수 있습니다.

완전하고 무제한인 탐색에서 마지막 상황이 발생해야만 수학적으로 ‘풀 수 없음’을 강하게 주장할 수 있습니다. 작은 온라인 도구는 보통 화면 응답성을 위해 처리량을 제한합니다. 한도 메시지가 나오면 보드를 줄이거나 교착을 확인하거나 역방향 계획을 해 보세요. 관련 소코반 솔버는 작은 보드용 한도를 설명하고 무한 실행 대신 명확한 메시지를 반환합니다.

레벨 제작자는 솔버로 경로를 확인하고 사람의 플레이 테스트로 의도한 학습이 전달되는지 점검할 수 있습니다. 소코반 레벨 설계 가이드는 그 과정을 다루며, 이 글은 그 아래에서 작동하는 탐색을 설명합니다.

소코반 솔버 알고리즘 FAQ

소코반 솔버 알고리즘이란 무엇인가요?

상자와 플레이어의 상태를 표현하고 합법적인 밀기를 생성하며, 알려진 교착 상태를 제외하고 모든 목표를 채우면 경로를 복원하는 탐색 절차입니다.

방향키 이동을 하나씩 모두 탐색하나요?

보통 걷기를 플레이어의 도달 가능 영역으로 묶고 밀기를 주요 간선으로 확장합니다. 따라서 결과가 같은 많은 걷기 경로를 탐색에서 제외할 수 있습니다.

교착 가지치기는 왜 탐색을 빠르게 하나요?

목표가 아닌 모서리, 움직이지 않는 상자 묶음, 막힌 통로 같은 분기를 후속 상태 탐색에 시간을 쓰기 전에 제거하기 때문입니다.

처음 찾은 경로가 최단 경로인가요?

선택한 탐색 순서와 비용 모델이 보장하는 경우에만 그렇습니다. 제한된 브라우저 솔버는 밀기 수나 전체 이동 수의 최적성을 증명하지 않고 실행 가능한 경로를 반환할 수 있습니다.

탐색 한도에 도달했다는 뜻은 무엇인가요?

경로의 존재나 불가능성을 증명하기 전에 안전한 처리 한도에서 멈췄다는 뜻입니다. 더 작은 보드로 시도하거나 상태를 직접 확인하세요. 해가 없다는 증거로 해석하면 안 됩니다.

출처와 참고 자료

상태와 도달 가능 영역 개념은 소코반 위키의 솔버 자료를 참고했습니다. 탐색 순서 예시는 소코반의 기본 탐색 알고리즘 해설에 따릅니다. 상태 공간 증가와 거리 추정의 한계는 Pavel Klavik의 소코반 솔버 문서에서 설명합니다. 이 자료는 표준 소코반을 다루며, 사이트 도구의 구체적인 한도는 링크된 Zeek 솔버를 기준으로 합니다.

작은 보드로 결과 확인하기

ASCII 보드를 브라우저 솔버에 붙여 넣고, 돌아와서 이동 문자열을 상태·밀기·가지치기 개념과 연결해 보세요.

소코반 솔버 열기