풀이

1. 먼저 실제 경기가 몇번 치뤄지는지 판단해보자. 총 6개국으로 구성되어 있으니, $_6C_2$ 이다. (순서는 신경 쓰지않고 2개를 뽑는 경우의 수다. 즉 15경기만 이뤄진다.

2. 1.에서 구한 경우의 수를 실제로 표현해보면, 아래의 표와 같다. (편의상 홈과 어웨이가 무조건 존재한다고 생각하고 문제를 풀어보자)

   Home	-	Away
   A	v	B,C,D,E,F
   B	v	C,D,E,F
   C	v	D,E,F
   D	v	E,F
   E	v	F

   위 표와 같은 경우의 수만 등장한다.

3. 이제 어떻게 할까? 각 경기에서 누가 이기고 졌는지 또는 비겼는지 일일이 값을 입력해보는 방법밖에 없다. 대신, 그렇게 모든 경우의 수를 탐색하게 되면, $3^{15}$만큼의 경우의 수가 존재하기 때문에 문제의 시간 제한 1초를 어길 수 밖에없다. 따라서, 백트래킹으로 특정 조건을 만족하면 escape하게 구현해야한다.

4. 그러면 어떻게 escape하게 만들어야 할까? 문제에 입력으로 주어진 값을 활용할 방법은 없을까? 실제로 각 경기마다 직접 입력값에 -1 연산을 진행해주면 음수가 되는 경우 그 이후는 탐색할 필요가 없어진다.

   ex)
   
   15개의 경기를 이어가는 과정에서 Home에 해당하는 팀(vs에서 왼쪽)이 계속 이기다 보면, 9번째 경우 B가 결국 실제 이긴 경기 수보다 많이 카운트 되어 -1이 된 것을 알 수 있다. 더 뒤에 탐색할 필요없이 pruning을 진행하면 된다. (pruning은 백트래킹에서 가지치기를 의미함)

5. 최종 15경기까지 무사히 들어갈 수 있다면, 그 경우는 실제로 가능한 경우인 것이다. 또한, 혹시 모를 예외 처리를 위해서 모든 연산이 다 마친 이후에 15경기까지 도달했다면, 각 팀이 가지는 [승,무,패] 전적을 모두 더해서 0이 나오는지 확인하면 된다.

6. 코딩 시작!

일단 4가지 경우기 때문에, 전체 테스트 케이스 for문을 선언하고, 각 팀의 전적을 센스있게 idx 설정해보자

from itertools import combinations

for test_case in range(4):
    game_result=list(map(int,input().split()))
    games=list(combinations(range(6),2))
    team_record=[]
    # team 성적 입력
    for i in range(6):
        team_record.append([game_result[3*i],game_result[3*i+1],game_result[3*i+2]])

games는 이전에 언급한 15가지의 경기를 의미하고, game_result에 미리 전 팀의 전적을 저장해둔 다음에, 6팀 각각의 팀 성적을 for in range(6): 과 3*i 를 활용해 접근해서 할당하자. (0,1,2 / 3,4,5 / 6,7,8 / 9,10,11 / 12,13,14 / 15,16,17) idx에 해당하는 값들을 접근해서 가져오면 된다.

def dfs(depth):
    global cnt
    if depth==15:
        cnt=1
        # 모든 팀의 기록이 0이 되어야 무사히 cnt
        for sub in team_record: 
            if sum(sub)!=0:
                cnt=0
                break
        return
    g1,g2=games[depth]
    # g1이 승리하고 g2가 패배하는 경우/ 무승부 / g1이 패배하고 g2가 승리하는 경우
    for x,y in ((0,2),(1,1),(2,0)): 
        if team_record[g1][x]>0 and team_record[g2][y]>0:
            team_record[g1][x]-=1
            team_record[g2][y]-=1
            dfs(depth+1)
            team_record[g1][x]+=1
            team_record[g2][y]+=1

depth를 15까지 도달하면, 무사히 적절한 경우의 수를 찾은 것이니 cnt=1을 부여해주지만, 팀의 기록이 0이 되어있지않고, 남아있는 예외가 있을 수 있으니 아래와 같이 미리 처리해둔다.

for sub in team_record: 
	if sum(sub)!=0:
    	cnt=0
        break

이전에 미리 combinations을 통해서 매칭 상대를 설정해뒀고 이는 A v.s B 부터 E v.s F 까지 차례대로 주어진다.

각 매치별로 g1(home)팀이 이기는 경우, 비기는 경우, 지는 경우를 모두 탐색해야하기 때문에, record에서의 각 위치를 활용한다.

g1,g2=games[depth]
    # g1이 승리하고 g2가 패배하는 경우/ 무승부 / g1이 패배하고 g2가 승리하는 경우
    for x,y in ((0,2),(1,1),(2,0)): 
        if team_record[g1][x]>0 and team_record[g2][y]>0:
            team_record[g1][x]-=1
            team_record[g2][y]-=1
            dfs(depth+1)
            team_record[g1][x]+=1
            team_record[g2][y]+=1

• (0,2) 는 home이 이기고, away가 지는 경우
• (1,1) 는 home과 away가 비기는 경우
• (2,0) 는 away가 이기고, home이 지는 경우

1씩 빼준 이후에, 재귀호출을 진행한다. 만약에 재귀호출된 이후에 조건을 성립하지 않는다면, (조건 : if team_record[g1][x]>0 and team_record[g2][y]>0: ) 아무일 없이 리턴하게 되고, 다음 경우(home이 이김 → 비김 → home이 짐)를 순서대로 검사하게 된다. 물론, 이전에 틀린 경우는 다시 +1 을 해주는 것으로 원상복구 해준다.

전체코드는 아래와 같다.

# 6987 월드컵
from itertools import combinations

def dfs(depth):
    global cnt
    if depth==15:
        cnt=1
        # 모든 팀의 기록이 0이 되어야 무사히 cnt
        for sub in team_record: 
            if sum(sub)!=0:
                cnt=0
                break
        return
    g1,g2=games[depth]
    # g1이 승리하고 g2가 패배하는 경우/ 무승부 / g1이 패배하고 g2가 승리하는 경우
    for x,y in ((0,2),(1,1),(2,0)): 
        if team_record[g1][x]>0 and team_record[g2][y]>0:
            team_record[g1][x]-=1
            team_record[g2][y]-=1
            dfs(depth+1)
            team_record[g1][x]+=1
            team_record[g2][y]+=1


answers=[]
for test_case in range(4):
    game_result=list(map(int,input().split()))
    games=list(combinations(range(6),2))
    team_record=[]
    # team 성적 입력
    for i in range(6):
        team_record.append([game_result[3*i],game_result[3*i+1],game_result[3*i+2]])

    # 실제 경우의 수 탐색
    cnt=0
    dfs(0)
    answers.append(cnt)

print(*answers)