[백준] 6987 월드컵 (Javascript)

문제

BOJ6987_월드컵

풀이

처음에는 그냥 2중 for문으로 풀 수 있지 않나 싶어서 도전해봤으나 틀렸다.

처음에 제출한 코드 (틀렸습니다)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs')
    .readFileSync(filePath)
    .toString()
    .trim()
    .split('\n')
    .map((row) => row.split(' ').map(Number));
const answer = [];
input.forEach((row) => {
    const arr = [];
    let possible = true;
    for (let i = 0; i < 6; i++) {
        arr.push(row.splice(0, 3));
    }
    for (let i = 0; i < 6; i++) {
        for (let j = 0; j < 6; j++) {
            if (i === j) continue;
            // 승, 패 비교
            if (arr[i][0] && arr[j][2]) {
                arr[i][0]--;
                arr[j][2]--;
            }
            if (arr[i][2] && arr[j][0]) {
                arr[i][2]--;
                arr[j][0]--;
            }
            // 무승부 끼리 비교
            if (arr[i][1] && arr[j][1]) {
                arr[i][1]--;
                arr[j][1]--;
            }
        }
    }
    for (let i = 0; i < 6; i++) {
        for (let j = 0; j < 3; j++) {
            if (arr[i][j] !== 0) possible = false;
        }
    }
    if (possible) answer.push(1);
    else answer.push(0);
});

console.log(answer.join(' '));

결국 다른 분들의 코드를 참고해서 건실하게 백트래킹으로 풀었다.

한 조에서 총 15경기(5+4+3+2+1)가 진행되고 한 경기에서 승, 패, 무승부 이렇게 비교해야 하는 경우가 3가지씩 늘어나니까, 시간복잡도는 $O(3^1$$^5)$가 된다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs')
    .readFileSync(filePath)
    .toString()
    .trim()
    .split('\n')
    .map((row) => row.split(' ').map(Number));
const answer = Array(4).fill(0);
input.forEach((row, index) => {
    const arr = [];
    const match = [];
    for (let i = 0; i < 6; i++) {
        arr.push(row.splice(0, 3));
    }
    // 대진표
    for (let i = 0; i < 6; i++) {
        for (let j = i + 1; j < 6; j++) {
            match.push([i, j]);
        }
    }

    backTracking(0, arr, match, index);
});

function backTracking(cur, arr, match, index) {
    if (cur === 15) {
        let possible = true;
        for (let i = 0; i < 6; i++) {
            for (let j = 0; j < 3; j++) {
                if (arr[i][j] !== 0) possible = false;
            }
        }
        if (possible) answer[index] = 1;
        return;
    }

    const [a, b] = match[cur];
  
    // 승, 패 비교
    if (arr[a][0] && arr[b][2]) {
        arr[a][0]--;
        arr[b][2]--;
        backTracking(cur + 1, arr, match, index);
        arr[a][0]++;
        arr[b][2]++;
    }
    // 패, 승 비교
    if (arr[a][2] && arr[b][0]) {
        arr[a][2]--;
        arr[b][0]--;
        backTracking(cur + 1, arr, match, index);
        arr[a][2]++;
        arr[b][0]++;
    }
    // 무승부 끼리 비교
    if (arr[a][1] && arr[b][1]) {
        arr[a][1]--;
        arr[b][1]--;
        backTracking(cur + 1, arr, match, index);
        arr[a][1]++;
        arr[b][1]++;
    }
}

console.log(answer.join(' '));