백준 6987. 월드컵 - 파이썬

문제

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

풀이과정

• 처음엔 전체 게임 수, 승패수 동일 여부, 무승부 팀의 짝수 여부로 판단하려고 함
  → 하지만 대충 생각해도 반례가 많음
  → 완탐으로 재풀이
• 문제 조건 재확인
  • 6개국 각 5경기. 총 6C2의 조합 = 15경기
  • python - combination 함수로 가능한 경우의 수 뽑기
  • 가능하면 1, 불가능하면 0 출력

∴ 가능한 결과 조합을 가지고 실제 게임 결과에서 빼가면서 완전탐색

전체코드

import sys
input = sys.stdin.readline

from itertools import combinations as cb
possible_result = list(cb(range(6),2))

def dfs(depth):
    global result
    if depth == 15: #불가능하다면 depth 15까지 오지 않음
        result = 1
        for g in game:
            if g.count(0) != 3 : #15까지 와도 최종적으로 [0,0,0]이 아닐 경우 불가능
                result = 0
                break
        return

    t1,t2 = possible_result[depth] # 비교할 결과조합 불러오기
    for r1,r2 in ((0,2), (1,1), (2,0)): #각 game에서 승, 무, 패 결과 비교 후 결과조합에 맞춰 빼기
        if game[t1][r1] >0 and game[t2][r2] >0:
            game[t1][r1] -=1
            game[t2][r2] -=1
            dfs(depth+1)
            game[t1][r1] += 1
            game[t2][r2] += 1


ans = []
for _ in range(4):
    all_game = list(map(int,input().split()))
    game = [all_game[i:i+3] for i in range(0,18,3)]
    result = 0
    dfs(0)
    ans.append(result)

print(*ans)