사천성(두 번 꺾기) 앱은 패를 두 장 고를 때마다 「이 두 장은 두 번 이내로 꺾이는 선으로 이어지는가」를 판정해요. 힌트로 없앨 수 있는 쌍을 찾을 때도 같은 판정을 모든 쌍에 써요. 이 글에서는 그 구조를 프로그램으로 소개해요.

생각법: 꺾인 횟수마다 넓혀 가기

선은 세로나 가로로 곧게 나아가다가 가끔 꺾여요. 그래서 첫 번째 패에서 다음처럼 조사해요.

  1. 꺾임 0번: 첫 번째 패에서 위아래·좌우로 빈 칸을 곧게 나아가요. 두 번째 패에 닿으면 이어져요.
  2. 꺾임 1번: 1에서 나아간 칸 하나하나에서 방향을 바꿔 다시 곧게 나아가요.
  3. 꺾임 2번: 2에서 나아간 칸 하나하나에서 방향을 바꿔 한 번 더 곧게 나아가요.

세 번째까지 두 번째 패에 닿지 않으면 두 번 이내의 꺾임으로는 이어지지 않아요. 곧게 나아가는 것은 패에 부딪히거나 판 바깥으로 나가는 곳까지예요.

판 바깥의 처리

선은 판 바깥 한 칸도 지날 수 있어요. 프로그램에서는 판 둘레에 빈 칸을 한 바퀴만큼 더한 판을 쓰면 바깥도 보통의 빈 칸으로 다룰 수 있어요. 6열×8행 판이라면 8열×10행 판으로 만들어 조사해요.

五索二萬三萬五索東南西北

이 그림 윗줄 양 끝의 5삭은 위쪽 바깥의 빈 칸을 지나 꺾임 2번으로 이어져요.

프로그램

JavaScript로 쓰면 다음과 같아요.

// board[r][c]는 패의 이름, 빈 칸은 null. 판 둘레에 빈 테두리를 한 칸씩 더해 두었다.
function canConnect(board, from, to) {
  const rows = board.length;
  const cols = board[0].length;
  const steps = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  // 지금 있는 칸과, 마지막에 나아간 방향(처음은 -1)
  let frontier = [[from[0], from[1], -1]];
  const seen = new Set();
  for (let turn = 0; turn <= 2; turn++) {
    const next = [];
    for (const [r0, c0, dir] of frontier) {
      for (let d = 0; d < 4; d++) {
        if (d === dir) continue;
        let r = r0;
        let c = c0;
        while (true) {
          r += steps[d][0];
          c += steps[d][1];
          if (r < 0 || c < 0 || r >= rows || c >= cols) break;
          if (r === to[0] && c === to[1]) return true;
          if (board[r][c] !== null) break;
          const key = r + ',' + c + ',' + d;
          if (!seen.has(key)) {
            seen.add(key);
            next.push([r, c, d]);
          }
        }
      }
    }
    frontier = next;
  }
  return false;
}
  • board는 둘레에 빈 테두리를 더한 판이에요. 패가 있는 칸에는 패의 이름, 빈 칸에는 null이 들어 있어요.
  • from과 to는 두 패의 [행, 열]이에요(테두리를 더한 판에서의 위치).
  • frontier는 지금의 꺾임 횟수로 닿을 수 있는 칸과, 그곳으로 나아간 방향의 목록이에요.
  • 같은 방향으로 곧게 나아가는 것은 앞 차례에서 이미 조사했으니 건너뛰어요(d === dir).
  • seen은 같은 칸에 같은 방향으로 닿은 것을 기억해 두어, 같은 조사를 되풀이하지 않기 위한 것이에요.

이 프로그램은 두 번째 꺾임 뒤에 곧게 나아간 끝에서 두 번째 패에 닿는지까지 조사해요. 패 위는 지날 수 없으니 부딪힌 곳에서 멈춰요(두 번째 패만은 닿은 곳에서 판정해요).

앱과의 대조

이 프로그램을 앱과 같은 선 찾는 방법(사이트 글의 그림에도 쓰는 계산)과 비교했어요. 앱과 같은 방식으로 만든 48장 판을 300게임 만들고, 중간까지 없앤 판도 포함해서 제각각 고른 패의 쌍 5044쌍으로 판정시켰더니, 이어진다·이어지지 않는다의 답은 모두 일치했어요.

앱에서는 이어질 때 화면에 선을 그리기 때문에, 이어지는지 여부뿐 아니라 꺾이는 모서리의 위치도 기억해 둬요. 선이 여러 가지일 때는 꺾임이 적은 선, 같다면 짧은 선을 골라 그려요.

없앨 수 있는 쌍을 모두 찾으려면

힌트처럼 없앨 수 있는 쌍을 찾을 때는 같은 그림 두 장의 쌍마다 이 프로그램으로 판정해요. 48장 판에서는 같은 그림의 조합이 72쌍이라서 많아야 72번의 판정으로 끝나요. 처음에 없앨 수 있는 쌍의 수는 처음에 없앨 수 있는 쌍은 몇 쌍?에서 세었어요.