들어가며

매일 아침에 푸는 알고리즘에서 시작했다. 문제를 쓱 훑어보고 씻고 밥을 먹으면서 로직이 떠오르고 풀기 시작했다. 그리고 왜 안돼? 고통받은지 3일만에 에러를 잡았다. 3일 내내 코딩하진 않았지만 계속 마음 속 짐처럼 나를 괴롭혔다. 다 풀린 것 같은데 왜 안되는걸까? 근데 레퍼런스 코드는 죽어도 보기 싫고. 아주 조금만 수정하면 해결될 것 같은!! 아!! 이거 아는데!! 사소하지만 중요한 기억이 떠오르지 않는 답답한 상황이었다.

여가 시간까지 스도쿠 문제를 풀다보니 마음이 조급해지면서 정신이 피폐해지고 밤 늦게까지 붙잡다가 다음날에 지장이 가고 수업 시간에도 문제가 떠올라서 나도 모르게 에디터를 열어서 풀다가 또 스트레스 받고!!! 나의 삶은 급격하게 황폐해졌다.

디버거를 써도 워낙 복잡한 로직으로 돌아가고 한 번 실행할 때 마다 브라우저가 뻗어버려서 원활하게 테스트 진행이 힘들었다. 그리고 오늘! 맑은 정신으로 곰곰히 생각하다가 취약점을 찾아냈고 드디어 문제를 해결했다. 그 삽질기를 정리해보고자 한다. 결론부터 말하자면 재귀 함수 다루기가 서툰게 이유였다.

문제

스도쿠는 숫자 퍼즐로, 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐입니다. 퍼즐을 푸는 방법은 아홉 가로줄, 세로줄, 3X3 칸에 1에서 9까지의 숫자를 중복되지 않게 한 번씩만 넣으면 됩니다. 일부 칸이 비어있는 상태인 스도쿠 보드를 입력받아 스도쿠 퍼즐이 완성된 보드를 리턴해야 합니다.

let board = [
  [0, 3, 0, 2, 6, 0, 7, 0, 1],
  [6, 8, 0, 0, 7, 0, 0, 9, 0],
  [1, 9, 0, 0, 0, 4, 5, 0, 0],
  [8, 2, 0, 1, 0, 0, 0, 4, 0],
  [0, 0, 4, 6, 0, 2, 9, 0, 0],
  [0, 5, 0, 0, 0, 3, 0, 2, 8],
  [0, 0, 9, 3, 0, 0, 0, 7, 4],
  [0, 4, 0, 0, 5, 0, 0, 3, 6],
  [7, 0, 3, 0, 1, 8, 0, 0, 0],
];
let output = sudoku(board);
console.log(output); // -->
/* 
[
  [4, 3, 5, 2, 6, 9, 7, 8, 1],
  [6, 8, 2, 5, 7, 1, 4, 9, 3],
  [1, 9, 7, 8, 3, 4, 5, 6, 2],
  [8, 2, 6, 1, 9, 5, 3, 4, 7],
  [3, 7, 4, 6, 8, 2, 9, 1, 5],
  [9, 5, 1, 7, 4, 3, 6, 2, 8],
  [5, 1, 9, 3, 2, 6, 8, 7, 4],
  [2, 4, 8, 9, 5, 7, 1, 3, 6],
  [7, 6, 3, 4, 1, 8, 2, 5, 9],
];
 */

재귀 함수에서 원본 배열 보존

재귀를 하면서 원본 배열을 보존하지 않자 수많은 문제가 생겼다. 재귀가 실패해서 다시 돌아가도 이전에 입력했던 값이 남아있어서 난장판으로 꼬이는게 debugger로 보였다. 2차원 배열이라 for문과 slice로 새로운 배열을 할당했다.

  function initBoard () {
    let iBoard = []
    for (let i=0; i < 9; i += 1) iBoard.push(board[i].slice())
    return iBoard;
  }

중복되는 수가 있는지 확인

하나씩 보면 x축과 y축 그리고 3*3 영역에 중복되는 수가 있는지 확인하는 함수다. 특별한 부분은 없었다. 3*3 영역의 계산은 타겟 좌표를 3으로 나누면서 나머지를 버린다. 다시 3을 곱해서 1씩 더해주면 간단하게 완성. 여기까진 괜찮았다.

 function checknewBoard (yTarget, xTarget) {
    let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    // x 배열 초기화
    let xArr = board[yTarget].slice()
    // y 배열 초기화
    let yArr = [];
    for (let i=0; i < 9; i += 1) yArr.push(board[i][xTarget])
    // 지역 배열 초기화 
    let areaArr = [];
    let areaX = Math.ceil((xTarget+1) / 3);
    let areaY = Math.ceil((yTarget+1) / 3);
    areaX = areaX === 4 ? 3 : areaX;
    areaY = areaY === 4 ? 3 : areaY;
    for (let y=0; y < 3; y += 1) {
      for (let x=0; x < 3; x += 1) {
        areaArr.push(board[y + ((areaY-1) * 3)][x + ((areaX-1) * 3)]) 
      }
    }
    // console.log(areaArr)
    // x축 확인
    numbers = numbers.filter((n) => !xArr.includes(n)) 
    // y축 확인
    numbers = numbers.filter((n) => !yArr.includes(n)) 
    // 3*3 확인
    numbers = numbers.filter((n) => !areaArr.includes(n)) 
    return numbers
  }

😱 끝나지 않는 재귀

엄청난 실수를 했다. 이 글을 쓰게된 이유다.

• for문이 총 3개 쓰였다. y축, x축 반복하는 for문 2개
• if문으로 0을 확인한다.
• 겹치지 않는 수의 배열을 받아온다.
• 다시 for문으로 겹치지 않는 수만큼 재귀 함수를 실행한다.
• 숫자를 하나 바꿔서 재귀가 끝나면 다음 좌표로 이동한다????????????????????

왜 이게 문제냐면, 모든 재귀를 마치더라도 y축과 x축을 돌아다니면서 다시 반복을 한다. [8][7]에서 끝난 재귀가 다시 [8][8]로 좌표를 받아서 재귀를 실행한다. 끝까지 보더라도 그럼 그 전 좌표가 다시 끝까지 좌표를 확인한다.
끝을 보더라도 거쳐왔던 모든 재귀 함수가 좀비처럼 좌표 끝까지 질주한다.

  let newBoard = [];
  for (let y=0; y < 9; y += 1) {
    for (let x=0; x < 9; x += 1) {
      if (board[y][x] === 0) {
        let numberArr = checknewBoard(y, x)
        if (numberArr.length === 0) return false;
        for (let el of numberArr) {
          newBoard = initBoard();
          newBoard[y][x] = el;
          //console.log(x, y, el, numberArr)
          //console.log(newBoard)
          debugger;
          sudoku(newBoard)
          // console.log(newBoard)
          if (Array.isArray(newBoard) && newBoard[8][8] !== 0) return newBoard;
        }
      }
    }
  }

😇 하나의 숫자만 바꾸는 재귀

• 좌표 확인하는 반복문에서 재귀 함수를 뺐다.
  비어있는 좌표 딱 하나만 받고 나머지는 무시한다.
• 비어있는 좌표 하나만 수정하고 가능성만큼 for문을 돌려 재귀를 부른다.
• 모든 재귀를 마치면 깔끔하게 끝난다.

이걸 생각 못해서 몇일동안 고통받았다니. 맵다. 문제를 깨달으면 해결은 순식간이다. 풀고나니 이게 뭐라고 이 고생을 한걸까? 다 내 잘못이다. 기본기가 부실한데 사용하려니 벌받은거다. 그리고... 이제 성불할 수 있다. 여러분 안녕...

  // 배열 깊은 복사
  let newBoard = initBoard();
  // 0 좌표 검색
  let target = [];
  for (let y=0; y < 9; y += 1) {
    for (let x=0; x < 9; x += 1) {
      if (target.length === 0 && board[y][x] === 0) {
        target = [y, x];
      }
    }
  }
  // 모든 숫자가 들어와 있을 때 현재 보드를 리턴 
  if (target.length === 0) return newBoard;

  let result = [];
  let numberArr = checknewBoard(target[0], target[1])
  if (numberArr.length === 0) return false;
  for (let el of numberArr) {
    newBoard[target[0]][target[1]] = el;
    result = sudoku(newBoard)
    if (Array.isArray(result) && result[8][8] !== 0) return result;
  }