문제

문제 링크
매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다.

매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26이 되기 때문이다. 위의 그림의 여섯 줄에 쓰여 있는 숫자는 다음과 같다.

1 + 4 + 10 + 11
11 + 5 + 3 + 7
7 + 6 + 12 + 1
2 + 10 + 5 + 9
9 + 3 + 6 + 8
8 + 12 + 4 + 2
매직 스타를 채우는 방법은 여러 가지가 있다. 일부만 채워진 매직 스타가 주어졌을 때, 수를 전부 다 채워서 매직 스타를 만드는 프로그램을 작성하시오.

입력

매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 위해서 사용하는 문자이다. 모든 입력은 예제 입력과 같은 형태로 주어진다.

출력

매직 스타를 만들 수 있는 방법 중에 사전 순으로 가장 앞서는 방법을 출력한다. (모든 줄을 순서대로 붙여서 하나의 문자열로 만든 뒤, 사전 순으로 비교한다.) 항상 정답이 존재하는 경우만 입력으로 주어진다.

예제 입력

....x....
.A.I.D.x.
..x...x..
.x.x.x.x.
....x....

예제 출력

....F....
.A.I.D.L.
..H...E..
.C.J.B.K.
....G....

풀이

보자마자 dfs와 백트래킹이 생각난 문제였다. 백트래킹 문제는 아직 많이 풀어보질 않아서 예전에 풀었던 N-Queen 문제를 생각하며 가로와 대각선을 다 체크해볼까 생각했지만, 매직 스타를 채우고 검증할 로직이 쉽게 떠오르지 않았다.

그래서 다른 방법으로 풀기로 결정. 매직스타의 크기는 정해져있고, 각 문자가 들어가는 좌표 값도 고정이다. 배열을 순회해서 비어있는 좌표값을 구하고, 문자가 채워져있는경우 알파벳 배열(A~L)에 사용했음을 체크해줬다. 그 뒤 dfs를 통해서 각 자리마다 알파벳을 순서대로 대입하여 매직스타를 채우고, 다 채웠을 경우 6개의 조건문을 통해 각 줄의 합이 26이 되는지 체크했다.

올바르게 채워진 매직스타가 여러개가 나올 수 있는데 문제에선 사전순으로 정렬된 제일 처음 매직스타를 출력하라고 제한되어있다. dfs를 통해 가장 처음 통과되는 매직스타가 문자 순서로도 제일 앞에 오는 매직스타이기에 이 점은 상관없으나, 첫 매직스타를 찾고나서도 dfs가 재귀적으로 모든 경우의 수를 찾다보니 시간 초과가 발생했다. 그래서 첫 매직스타를 찾고나면 플래그를 세워주고, 각 dfs 실행마다 플래그를 체크해 함수를 조기종료 시켰다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../ex.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const hexagram = input.map((item) => item.split(""));
// 완성된 매직스타 치환할때 사용
const alp = [0, ..."ABCDEFGHIJKL".split("")];
// 사용한 알파벳 목록들의 배열
const visited = [0, ..."ABCDEFGHIJKL".split("")];
// 매직스타의 비어있는 칸 좌표 값 저장할 배열
const arr = [];
// dfs 조기 종료 플래그
let isFind = false;

// 비어있는 좌표 및 사용한 문자 탐색, 매직스타의 문자를 숫자로 치환
hexagram.forEach((item, idx) =>
  item.forEach((item2, idx2) => {
    if (item2 !== "." && item2 !== "x") {
      const alpIdx = visited.indexOf(item2);
      visited[alpIdx] = 0;
      hexagram[idx][idx2] = alpIdx;
    }

    if (item2 === "x") {
      arr.push([idx, idx2]);
    }
  })
);

function dfs(num) {
  if (num === arr.length) {
    if (check()) {
      const answer = hexagram.map((item) =>
        item.map((item2) => {
          if (item2 !== ".") {
            item2 = alp[item2];
          }
          return item2;
        })
      );
      isFind = true;
      console.log(answer.map((item) => item.join("")).join("\n"));
    }
    return;
  }

  if (isFind) return;

  for (let i = 0; i < visited.length; i++) {
    if (visited[i] !== 0) {
      const alphabet = visited[i];
      hexagram[arr[num][0]][arr[num][1]] = i;
      visited[i] = 0;
      dfs(num + 1);
      hexagram[arr[num][0]][arr[num][1]] = "x";
      visited[i] = alphabet;
    }
  }
}

// 매직스타 검증 함수
function check() {
  if (hexagram[0][4] + hexagram[1][3] + hexagram[2][2] + hexagram[3][1] !== 26)
    return false;
  if (hexagram[0][4] + hexagram[1][5] + hexagram[2][6] + hexagram[3][7] !== 26)
    return false;
  if (hexagram[1][1] + hexagram[1][3] + hexagram[1][5] + hexagram[1][7] !== 26)
    return false;
  if (hexagram[1][1] + hexagram[2][2] + hexagram[3][3] + hexagram[4][4] !== 26)
    return false;
  if (hexagram[1][7] + hexagram[2][6] + hexagram[3][5] + hexagram[4][4] !== 26)
    return false;
  if (hexagram[3][1] + hexagram[3][3] + hexagram[3][5] + hexagram[3][7] !== 26)
    return false;
  return true;
}

dfs(0);