[Algorithm🧬] 백준 6987 : 월드컵

문제

처음에 경우의 수로 생각

반례
0 5 0
0 5 0
0 5 0
0 5 0
2 0 3
3 0 2

무는 횟수 카운트만 맞는다고 존재할 수 있는게 아니었음..!

import sys

readl = sys.stdin.readline


def sol(inp):
    # 데이터 처리
    results = []
    for j in range(6):
        results.append(inp[3 * j: 3 * (j + 1)])

    # 한 팀의 경기 횟수는 5회여야 함.
    for i in range(6):
        if sum(results[i]) != 5:
            return False

    # 총 경기 수는 30회여야 함.
    if sum(inp) != 30:
        return False

    # 승리 횟수와 패배 횟수가 같아야함.
    if sum(inp[0::3]) != sum(inp[2::3]):
        return False


    # 무가 N회 있으려면 다른 쪽에도 무가 N회 있어야함.
    # 2 2 라고 생각했는데 생각해보니 같은 팀이랑 두번 경기를 할 수가 없어서 이건 아님..
    # 그리고 무에 대한 조건을 다 따질 수가 없음...
    ch = []
    for i in range(6):
        if results[i][1] != 0:
            ch.append(results[i][1])

    while ch:
        c = ch.pop(0)
        if c in ch:
            ch.remove(c)
        else:
            return False

    return True



for i in range(4):
    inp = list(map(int, readl().split()))
    print(1 if sol(inp) else 0, end=' ')

DFS

느낌 상 DFS 같긴 했는데 이건 어떤 방식으로 세워야할지 몰라서...
여기 를 참고해서 풀었다.

import sys

readl = sys.stdin.readline

def DFS(play):
    global ans
    if play == 15:
        ans = 1
        for r in results:
            if r.count(0) != 3:
                ans = 0
                break
        return

    home, away = 대진표[play]

    # 가능한 경우 3가지
    # 승 패 / 무 무 / 패 승
    for x, y in ((0, 2), (1, 1), (2, 0)):
        if results[home][x] > 0 and results[away][y] > 0:
            results[home][x] -= 1
            results[away][y] -= 1
            DFS(play + 1)
            results[home][x] += 1
            results[away][y] += 1




# 15번의 경기를 진행.
대진표 = []
for i in range(6):
    for j in range(i + 1, 6):
        대진표.append((i, j))


for i in range(4):
    inp = list(map(int, readl().split()))
    results = [inp[3 * i : 3 * (i + 1)] for i in range(6)]

    ans = 0
    DFS(0)
    print(ans, end=' ')