합이 10인 조합이 남았는지 판정하기 (연결 부분집합 열거)

왜 공부했나

블로그에 사과게임(17×10 판에서 인접한 칸을 긁어 합이 정확히 10이면 사라지는 게임)을 만들었다. 2분 제한인데, 판에 조합이 하나도 안 남았는데도 남은 시간 동안 멍하니 긁고 있어야 하는 게 답답했다.

그래서 “더 이상 만들 수 있는 조합이 없으면 즉시 종료"를 넣기로 했다. 문제는 그 판정이다. 지금 판에 합이 10이 되는 연결 부분집합이 하나라도 있는가?

순진하게 접근하면

170칸의 모든 부분집합을 보는 건 당연히 불가능하다. 2¹⁷⁰이다.

하지만 조건이 두 개 있어서 실제 탐색 공간은 훨씬 작다.

  1. 연결되어 있어야 한다 — 상하좌우로 이어진 덩어리만 유효하다
  2. 값이 전부 1~9의 양수다 — 합이 10을 넘는 순간 그 가지는 죽는다

특히 2번이 강력하다. 양수만 있으니 합은 단조 증가하고, 유효한 조합의 크기는 최대 10칸(전부 1일 때)이다. 깊이가 10으로 묶인다.

프론티어 확장 + 포함/제외 분기

연결 부분집합을 만드는 표준적인 방법은 씨앗에서 시작해 경계(프론티어)를 넓히는 것이다.

  • 씨앗 칸 하나를 고정하고 시작
  • 프론티어 = 지금 덩어리에 인접한, 아직 결정하지 않은 칸들
  • 프론티어에서 칸을 하나 꺼내 포함 / 제외로 분기
  • 포함하면 그 칸의 이웃들이 프론티어에 추가된다
flowchart TD
    S["씨앗 s 선택<br/>합 = num s"]
    F{"프론티어에<br/>결정할 칸 v 가 있나"}
    N["실패 — 이 씨앗으로는 못 만듦"]
    C{"합 + v ≤ 10 인가"}
    I["v 포함<br/>v의 이웃을 프론티어에 추가"]
    E["v 제외<br/>forbidden 처리"]
    W["합 == 10 → 성공"]

    S --> F
    F -- 없음 --> N
    F -- 있음 --> C
    C -- 예 --> I
    I --> W
    I --> F
    C -- 아니오 --> E
    E --> F

코드로는 이렇게 됐다.

// 프론티어에서 한 칸씩 '포함 / 제외'로 분기 → 연결 부분집합을 중복 없이 열거
function rec(frontier, sum){
  if(sum === 10) return true;
  let v = -1, fi = -1;
  for(let i=0;i<frontier.length;i++){ if(valid(frontier[i])){ v = frontier[i]; fi = i; break; } }
  if(v < 0) return false;
  const rest = frontier.slice(0, fi).concat(frontier.slice(fi+1));
  const vv = num[Math.floor(v/COLS)][v % COLS];
  if(sum + vv <= 10){                       // 포함
    chosen[v] = 1;
    const nf = rest.slice();
    nbrs(v).forEach(function(j){ if(valid(j) && nf.indexOf(j) < 0) nf.push(j); });
    if(rec(nf, sum + vv)){ chosen[v] = 0; return true; }
    chosen[v] = 0;
  }
  forbidden[v] = 1;                          // 제외
  const res = rec(rest, sum);
  forbidden[v] = 0;
  return res;
}

중복 없이 세는 방법

여기가 제일 헷갈렸던 부분이다. 아무 칸이나 씨앗으로 삼아 전부 돌리면, 같은 덩어리를 칸 개수만큼 중복해서 열거하게 된다. {A,B,C}를 A에서도, B에서도, C에서도 만든다.

해결은 정규형(canonical form)을 정하는 것이다. 각 덩어리를 “그 안에서 인덱스가 가장 작은 칸"에서만 만들어지게 강제한다.

function valid(j){
  if(j <= seed || chosen[j] || forbidden[j]) return false;
  ...
}

j <= seed를 막으면, 씨앗보다 작은 인덱스는 절대 덩어리에 못 들어온다. 따라서 모든 연결 부분집합은 자기 최소 인덱스가 씨앗일 때 정확히 한 번만 열거된다.

forbidden도 같은 목적이다. 한 번 “제외"로 분기한 칸이 나중에 다른 경로로 다시 들어오면 같은 집합을 두 번 세게 된다. 분기하는 동안 잠가둔다.

전체 판정은 씨앗을 인덱스 순으로 돌리면 끝난다.

function hasCombo(){
  const total = ROWS * COLS;
  for(let seed=0; seed<total; seed++){
    const sr = Math.floor(seed/COLS), sc = seed % COLS;
    if(num[sr][sc] === 0) continue;
    if(seedReaches10(seed)) return true;
  }
  return false;
}

하나라도 찾으면 즉시 true라 실제로는 대부분 초반에 끝난다. 조합이 정말 없는 마지막 판정만 전체를 다 돈다.

구멍이 생기면 이웃이 달라진다

여기서 예상 못 한 게 하나 나왔다. 원래 사과게임은 사과가 치워져 생긴 빈 칸을 건너뛰고 같은 줄의 다음 사과를 인접으로 취급한다. 7 _ 3이면 7과 3이 이어진다. 단, 사이에 다른 사과가 있으면 거기서 막힌다 (7 9 3은 7과 3이 안 이어짐).

이걸 반영하려면 탐색 알고리즘을 고칠 게 아니라 이웃의 정의만 바꾸면 된다.

function nextApple(r,c,dr,dc){
  let rr = r + dr, cc = c + dc;
  while(rr >= 0 && rr < ROWS && cc >= 0 && cc < COLS){
    if(num[rr][cc] !== 0) return [rr,cc];   // 빈 칸은 건너뛰고 첫 사과
    rr += dr; cc += dc;
  }
  return null;
}

nbrs()가 이걸 쓰도록 바꾸니 백트래킹 코드는 한 줄도 안 건드렸다. 격자 위를 걷는 문제가 아니라 그래프 위를 걷는 문제로 보면, 판이 변할 때 바뀌는 건 간선뿐이다.

더 좋았던 건, 사용자가 직접 긁을 때의 인접 판정도 같은 함수를 쓴다는 점이다.

// 빈 칸(구멍)을 건너뛴 '다음 사과'가 이미 영역에 있으면 인접으로 본다.
function adjToRegion(r,c){
  for(let i=0;i<DIRS4.length;i++){
    const na = nextApple(r, c, DIRS4[i][0], DIRS4[i][1]);
    if(na && selSet[key(na[0], na[1])]) return true;
  }
  return false;
}

이웃 정의가 한 곳에 모여 있으니 “조기 종료가 떴는데 사실은 만들 수 있는 조합이 있었다” 같은 불일치가 구조적으로 생길 수 없다. 판정 로직과 입력 로직이 같은 그래프를 본다.

덤: 긁기를 경로가 아니라 영역으로

처음 긁기 구현은 “마지막 칸에만 이어붙는 뱀 경로"였다. 그래서 십자나 가지 갈라진 모양을 만들 수 없었고, 중심으로 되돌아가면 오히려 칸이 취소됐다.

adjToRegion으로 바꾸면서 지금까지 긁은 영역 중 어느 칸과라도 인접하면 추가로 규칙이 바뀌었다. 임의의 연결 모양을 만들 수 있게 됐고, 이게 위의 부분집합 열거가 찾는 “연결 부분집합"과 정확히 같은 정의가 됐다. 판정과 조작이 같은 개념 위에 서게 된 것이다.

채점 시점도 옮겨야 했다. 드래그 중에 합이 10에 닿는 순간 자동으로 터뜨렸더니, 그냥 누르고 비비기만 해도 영역이 커지다 10을 스쳐서 점수가 올라갔다. 손을 뗄 때만 채점하도록 바꿨다.

function endDrag(){
  if(!dragging) return;
  dragging = false;
  const ok = sel.length && selSum() === GOAL;
  if(mode === 'multi'){ if(ok) submitClear(); else cancelSel(); }
  else { if(ok) clearMatched(); else cancelSel(); }
  updateHud();
}

중간 상태를 확정으로 취급하지 말 것 — 앞서 온라인 대전에서 배운 것과 같은 교훈이다.

정리

  • 연결 제약 + 양수 = 탐색 공간이 확 준다. 깊이가 10으로 묶이고 합이 넘으면 즉시 가지치기
  • 중복 열거는 정규형으로 막는다. “최소 인덱스가 씨앗"이라는 규칙 하나로 각 부분집합이 정확히 한 번만 생성된다
  • 격자가 아니라 그래프로 보면 규칙 변경이 싸진다. 구멍 건너뛰기는 nbrs() 한 곳만 바꿔서 끝났다
  • 판정과 입력이 같은 이웃 정의를 공유하게 한다. 두 벌로 두는 순간 어긋난다
  • 중간 상태로 채점하지 않는다. 확정 시점을 명확히 잡는다