[백준/python]6987번 월드컵 - DFS

문제 출처 - https://www.acmicpc.net/problem/6987

제발 시간 복잡도 계산했는데 안되면 다른 방법을 생각하자. 처음에는 결과 배열 마다 따로 함수를 수행하지 않고 마지막 15 라운드에서 4개의 배열과 각각 비교하는 방식으로 풀었다. 결과 배열에서 -1을 하며 재귀를 수행하는 것이 아니라 0에서 부터 모든 경우를 구하기 때문에 가지치기를 할 수 있는 방법이 없다. 즉 시간 복잡도가 O(3**15)가 된다. (아슬아슬하게 틀리는 것 같다.) 결과 배열에서 -1을 하며 재귀를 수행하면 가지치기가 가능해서 쉽게 풀 수 있다.

1. 풀이

• 각각의 결과 배열마다 DFS 함수를 수행하여 가능한 결과인지 판단한다.
• 6팀이 경기할 수 있는 경우의 수는 총 15가지이다. home,away에 순서쌍을 인자로 넣어 재귀함수를 수행한다.
• 재귀 함수마다 home이 이긴 경우, 비기는 경우, 지는 경우에 결과 배열에서 -1을 한 뒤 다음 재귀로 넘긴다. 이 때 결과 배열의 값이 0보다 작다면 수행하지 않는다.
• 마지막 E와 F 경기까지 재귀 함수를 수행하고 얻은 결과 배열이 가능한 결과라면 [ [0,0,0] for _ in range(6) ] 일 것이다.

2. 코드

from itertools import combinations

def DFS(home,away):
    global L, tmp
    
    if away==6:
        home+=1
        away=home+1
    
    if home==5:
        if L==[ [0,0,0] for _ in range(6) ]:
            tmp=1
        return

    #home이 이긴경우
    if L[home][0]>0 and L[away][2]>0:
        L[home][0], L[away][2] = L[home][0]-1, L[away][2]-1
        DFS(home,away+1)
        L[home][0], L[away][2] = L[home][0]+1, L[away][2]+1
    
    #home이 지는경우
    if L[home][2]>0 and L[away][0]>0:
        L[home][2], L[away][0] = L[home][2]-1, L[away][0]-1
        DFS(home,away+1)
        L[home][2], L[away][0] = L[home][2]+1, L[away][0]+1
    
    #비기는 경우
    if L[home][1] and L[away][1]>0 :
        L[home][1], L[away][1] = L[home][1]-1, L[away][1]-1
        DFS(home,away+1)
        L[home][1], L[away][1] = L[home][1]+1, L[away][1]+1

sol = []
for round in range(4):
    question = list(map(int, input().split())) 
    L = []
    for i in range(6):
        L.append([question[i*3],question[(i*3)+1],question[(i*3)+2] ])
    
    tmp = 0
    DFS(0,1)
    sol.append(tmp)
    
print(*sol)