[백준] 6987번 : 월드컵

https://www.acmicpc.net/problem/6987

6987번: 월드컵

문제

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다. 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.

출력

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

코드

from itertools import combinations

game = list(combinations(range(6), 2))

def dfs(round):
    global ans
    if round == 15:
        ans = 1
        for sub in graph:
            if sub.count(0) != 3:
                ans = 0
                break
        return

    t1, t2 = game[round]
    for x, y in ((0, 2), (1, 1), (2, 0)):
        if graph[t1][x] > 0 and graph[t2][y] > 0:
            graph[t1][x] -= 1
            graph[t2][y] -= 1
            dfs(round+1)
            graph[t1][x] += 1
            graph[t2][y] += 1

answer = []
for _ in range(4):
    data = list(map(int, input().split()))
    graph = [data[i:i+3] for i in range(0, 16, 3)]
    ans = 0
    dfs(0)
    answer.append(ans)

print(*answer)

1. A, B, C, D, E, F 6개국은 한 번씩 싸워야 하므로 이것을 Combinations를 통해 나타낸다.

 

2. 6개국이 한 번씩 싸우면 총 (5+4+3+2+1) = 15경기를 진행해야 한다.

 

3. 경기를 치를 때마다 경우의 수는 총 3가지이다. ((t1승, t2패), (t1무, t2무), (t1패, t2승))

 

4. 만약 t1은 승리하였는데 t2가 패배한 경우가 없다면 이것은 불가능한 결과이다(반대의 경우도 마찬가지).

 

5. 경기를 치를 때마다 경기 결과를 하나씩 빼준다.(ex. t1승, t2패한 결과를 -1)

 

6. 15경기를 모두 치뤘는데 0이 아닌 결과가 있다면 불가능한 결과이다.

 

7. 이 최종 결과를 answer에 저장한다.