# AI 꾸러미 — 너비 우선 퍼즐 풀이 (상태 공간 겹 수) — Breadth-first search (BFS)
> 처음 판에서 한 번 · 두 번 … 움직여 닿는 판을 겹겹이 넓혀 가서, 목표 판에 처음 닿은 겹이 가장 짧은 풀이가 되게 한다.  
> 견본: https://ai-techstudio.web.app/#t/i354

이 문서를 코드 도우미(Claude Code · Cursor · ChatGPT 등)에 그대로 주면 돼요. 「## 주문서」 가 할 일, 나머지는 참고 자료예요.

## 주문서

### 만들어 줘: 너비 우선 퍼즐 풀이 (상태 공간 겹 수) — Breadth-first search (BFS)

#### 1. 목표
2×3 슬라이딩 퍼즐을 너비 우선 탐색으로 풀어 줘 — 가장 짧은 풀이와 겹마다 판 수를 보여 주게. 분위기는 겹이 동심원처럼 퍼지는 설명.

#### 2. 핵심 기술 용어
- **Breadth-first search (BFS)** — 가까운 판부터 겹겹이 넓혀 가는 탐색
- **State space** — 퍼즐이 될 수 있는 모든 판 — 마디 = 판, 가지 = 한 번 움직임
- **Visited set · parent links** — 이미 본 판은 건너뛰기 · 어디서 왔는지 기록해 길 되짚기

#### 3. 환경
- 플랫폼: TypeScript (브라우저), 라이브러리 없이 — 화면과 떨어진 순수 함수로
- 화면: 브라우저 — PC · 폰 모두

#### 4. 조건
- 방문 표(Set)로 같은 판을 두 번 넣지 않는다
- 큐는 shift() 대신 앞 인덱스만 늘려 쓴다 (shift 는 느리다)
- 판은 문자열 · 정수 열쇠로 묶는다
- 부모 기록으로 풀이 길을 되짚기
- 설명 화면: 겹마다 판 수 막대 + 처음 판(가운데)에서 겹이 퍼지는 그림 + 금빛 풀이 길

#### 5. 완성 기준 (이게 보이면 성공)
- 찾은 풀이의 움직임 수가 거리 표(목표에서 거꾸로 BFS)의 값과 같다
- 겹마다 판 수 막대가 보이고 목표에 닿은 겹에서 멈춘다
- 금빛 길을 따라 퍼즐이 실제로 풀린다

#### 6. 진행 방식
- 핵심 코드 위주로, 설명은 짧게. 내 프로젝트에 끼워 넣기 쉬운 함수 · 클래스로 나눠 줘.
- 처음 화면에 바로 결과가 보이게, 그리고 켬/끔(또는 전/후) 비교를 할 수 있게 만들어 줘.
- 그림 · 소리 · 모델 파일이 필요하면 코드로 만든 임시 대체물로 먼저 돌아가게 하고, 진짜 파일로 바꿀 자리를 표시해 줘.
- 마지막에 「확인 방법」(무엇을 보면 성공인지)과 「조절할 값」 목록을 짧게 정리해 줘.
- 답변과 코드 주석은 한국어로 해 줘.

## 원리
- 처음 판을 큐에 넣는다. 큐에서 판을 하나씩 꺼내, 한 번 움직여 갈 수 있는 판 중 처음 보는 것만 큐 뒤에 넣는다.
- 그러면 큐에는 「0번 움직인 판 → 1번 → 2번 …」 순서로 쌓인다 — 겹(깊이)이 고르게 넓어진다.
- 목표 판이 처음 나온 순간의 겹 수 = 가장 적은 움직임 수. 부모 기록을 따라 거꾸로 가면 풀이 길.
- 목표에서 거꾸로 한 번 돌리면(견본 SL_DIST) 모든 판까지의 거리 표가 생겨 — 판 만들기(가장 먼 판 고르기) · 힌트에 쓴다.

## 핵심 코드 — 2×3 슬라이딩 퍼즐 너비 우선 풀이
(발췌: demos/demosGameAI.ts slNext() · I354 gen() 을 정리)
```ts
const GOAL = '123450';                       // 0 = 빈칸
function next(s: string): string[] {
  const z = s.indexOf('0'), r = Math.floor(z / 3), c = z % 3;
  const out: string[] = [];
  for (const [dr, dc] of [[0, 1], [1, 0], [0, -1], [-1, 0]] as [number, number][]) {
    const nr = r + dr, nc = c + dc;
    if (nr < 0 || nr > 1 || nc < 0 || nc > 2) continue;
    const j = nr * 3 + nc, a = s.split('');
    a[z] = a[j]!; a[j] = '0';
    out.push(a.join(''));
  }
  return out;
}

function solve(start: string): string[] | null {
  const parent = new Map<string, string | null>([[start, null]]);
  const q = [start];
  for (let i = 0; i < q.length; i++) {        // shift 대신 인덱스
    const s = q[i]!;
    if (s === GOAL) {
      const path: string[] = [];
      for (let p: string | null = s; p; p = parent.get(p)!) path.unshift(p);
      return path;                             // 처음 닿은 겹 = 가장 짧은 풀이
    }
    for (const n of next(s)) if (!parent.has(n)) { parent.set(n, s); q.push(n); }
  }
  return null;                                 // 닿지 못함 (풀 수 없는 판)
}
```

## 흔한 실수 · 확인 목록
- [ ] **방문 표 없이 넓히면 같은 판을 수없이 다시 넣어 멈춘다** — 넣을 때 바로 방문 표에 기록한다 (꺼낼 때가 아니라).
- [ ] **큐를 shift() 로 꺼내면 판이 많을 때 느리다** — 배열 앞 인덱스만 늘린다 — 견본 for (i = 0; i < q.length; i++).
- [ ] **판을 배열 그대로 열쇠로 쓰면 Set 이 같은 판을 못 알아본다** — 문자열 · 정수로 묶는다. 같은 크기 블록은 구별하지 않게 묶으면 판 수도 준다.

## 완성 기준 체크리스트
- [ ] 찾은 풀이의 움직임 수가 거리 표(목표에서 거꾸로 BFS)의 값과 같다
- [ ] 겹마다 판 수 막대가 보이고 목표에 닿은 겹에서 멈춘다
- [ ] 금빛 길을 따라 퍼즐이 실제로 풀린다

## 이 기술 정보
- id: `i354` · 분류: 게임 시스템 · AI › 게임 AI · 공통 · 난이도 쉬움 · 폰 부담 가벼움 (폰 OK) — 본 판 수만큼 메모리. 2×3 퍼즐 360판, 주차장 단계는 수만 판 — 판을 짧은 문자열 · 정수로 묶어야 가볍다.
- 라이브 견본 (브라우저에서 직접 조작): https://ai-techstudio.web.app/#t/i354
- 쓰면 좋을 때: 움직임 한 번 비용이 모두 같은 퍼즐 (주차장 · 장난감 상자 · 얼음 별 · 창고지기) / 가장 짧은 풀이 · 힌트 · 「몇 수 만에 풀 수 있나」가 필요할 때
- 쓰지 말 때: 판 수가 수억이 넘는 퍼즐 — A* (거리 짐작) 나 양쪽에서 탐색 / 움직임마다 비용이 다를 때 — 다익스트라

## 견본 실제 코드 (라이브 견본이 돌리는 코드 — three.js · TypeScript)
### slNext — `src/demos/demosGameAI.ts:2946`
```ts
function slNext(s: string): string[] {
  const z = s.indexOf('0');
  const r = Math.floor(z / 3);
  const c = z % 3;
  const out: string[] = [];
  for (const [dr, dc] of [[0, 1], [1, 0], [0, -1], [-1, 0]] as [number, number][]) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr < 0 || nr > 1 || nc < 0 || nc > 2) continue;
    const j = nr * 3 + nc;
    const a = s.split('');
    a[z] = a[j]!;
    a[j] = '0';
    out.push(a.join(''));
  }
  return out;
}
```

## 관련 기술
- 다음에 해 볼 기술: [백트래킹 (8 여왕)](https://ai-techstudio.web.app/ai/t/i355.md) `i355` · [같은 판 기억 (전치표 · 조브리스트 해시)](https://ai-techstudio.web.app/ai/t/i344.md) `i344`
- 참고 문서: [Wikipedia — Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search)