백준[6987] 월드컵 (Python3)

정직하게 풀어야 했는데 편법쓰다 3번 틀린 문제
증명하는 방법이 복잡했기 때문에 완전 탐색으로 가야 했다.

 

 

동일한 조의 국가들은 다른 국가들과 1번씩 경기를 해서, 각 국가는 총 5번의 경기를 해야 한다.
따라서, 국가들이 경기를 하는 모든 경우의 수를 구한 다음 해당 국가끼리 경기를 했을 때,
이긴 경우, 비긴 경우, 진 경우 3가지에 대해 탐색을 한다.
총 15번의 경기를 하고, 매 경기마다 생기는 경우의 수가 3개이니 시간 복잡도는 O(3^15)이다

 

코드

import itertools

records = [[0 for _ in range(3)] for _ in range(6)]
match = list(itertools.combinations(range(6), 2))
ans = 0


def main():
    global ans
    for i in range(4):
        win, draw, loss = [], [], []
        result = list(map(int, input().split()))
        for j in range(0, 16, 3):
            win.append(result[j])
            draw.append(result[j + 1])
            loss.append(result[j + 2])
        ans = 0
        dfs(0, win, draw, loss)
        print(ans, end=" ")


def dfs(count, win, draw, loss):
    if count == 15:
        global ans
        if win.count(0) == 6 and draw.count(0) == 6 and loss.count(0) == 6:
            ans = 1
        return

    home, away = match[count]
    if win[home] > 0 and loss[away] > 0:
        win[home] -= 1
        loss[away] -= 1
        dfs(count + 1, win, draw, loss)
        win[home] += 1
        loss[away] += 1
    if draw[home] > 0 and draw[away] > 0:
        draw[home] -= 1
        draw[away] -= 1
        dfs(count + 1, win, draw, loss)
        draw[home] += 1
        draw[away] += 1
    if loss[home] > 0 and win[away] > 0:
        loss[home] -= 1
        win[away] -= 1
        dfs(count + 1, win, draw, loss)
        loss[home] += 1
        win[away] += 1


if __name__ == "__main__":
    main()