💡문제 분석 요약

• 6개의 국가가 월드컵에서 경기를 치르고, 각 경기에 대한 승패 또는 무승부 결과가 주어지는데, 주어진 결과가 실제로 가능한지 여부를 확인하는 문제이다.
• 경기 결과는 총 15번의 경기에서 승-패, 무승부-무승부, 패-승 중 하나로 결정되며, 모든 결과가 적절하게 배분되어야 한다.

💡알고리즘 설계

• 경기 조합 생성: 6개의 국가가 서로 경기하는 조합은 총 15가지이다. 이 조합을 미리 계산해 두고, 각 경기마다 승패나 무승부를 적용한다.
• 백트래킹 재귀 탐색: 각 경기에 대해 3가지 가능한 결과(승리-패배, 무승부, 패배-승리)를 시도하면서 해당 결과에 맞게 국가별 승/무/패 카운트를 조정한다. 모든 경기를 처리한 후, 각 국가의 카운트가 0이면 유효한 결과로 간주한다.
• 백트래킹을 통한 되돌리기: 경기에 대한 결과를 적용한 후, 재귀적으로 다음 경기를 처리하고, 탐색이 끝난 후에는 원래 상태로 되돌린다. 이를 통해 다른 가능한 경우도 탐색할 수 있다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n');

const data = [];

// 6개의 국가 정보 저장
for (let i = 0; i < 4; i++) {
  const temp = input[i].split(' ').map(Number);
  const nation = [];
  for (let j = 0; j < 6; j++) {
    nation.push([temp[j * 3], temp[j * 3 + 1], temp[j * 3 + 2]]);
  }
  data.push(nation);
}

const cases = [];

// 경기 조합 미리 계산
for (let i = 0; i < 6; i++) {
  for (let j = i + 1; j < 6; j++) {
    cases.push([i, j]);
  }
}

let possible = false;

function backtracking(round, nations) {
  if (round === 15) {
    if (nations.every(nation => nation.every(count => count === 0))) {
      possible = true;
    }
    return;
  }

  const [n1, n2] = cases[round];

  // 승-패
  if (nations[n1][0] > 0 && nations[n2][2] > 0) {
    nations[n1][0]--;
    nations[n2][2]--;
    backtracking(round + 1, nations);
    
    nations[n1][0]++;
    nations[n2][2]++;
  }

  // 무승부
  if (nations[n1][1] > 0 && nations[n2][1] > 0) {
    nations[n1][1]--;
    nations[n2][1]--;
    backtracking(round + 1, nations);

    nations[n1][1]++;
    nations[n2][1]++;
  }

  // 패-승
  if (nations[n1][2] > 0 && nations[n2][0] > 0) {
    nations[n1][2]--;
    nations[n2][0]--;
    backtracking(round + 1, nations);

    nations[n1][2]++;
    nations[n2][0]++;
  }
}

// 4개의 테스트 케이스에 대해 각각 처리
for (let t = 0; t < 4; t++) {
  possible = false;
  backtracking(0, data[t]);

  console.log(possible ? 1 : 0);
}

💡시간복잡도

• 15번의 경기에서 각각 3가지 결과를 고려하므로, 시간 복잡도는 O(3^15)이다.
• 이는 약 14,348,907번의 경우의 수를 탐색해야 하므로, 백트래킹으로 탐색을 줄이는 것이 중요하다.

💡 틀린 이유