[Algorithm] 백준 알고리즘 - 6987

문제(1309번)

문제 바로가기

내가 푼 답(다시 풀어보기)

import sys
from itertools import combinations

input = sys.stdin.readline

def dfs(depth):
    global result
    if depth == 15:
        result = 1
        for i in scores:
            if i.count(0) != 3:
                result = 0
                break
        return
    
    a, b = num_cases[depth]
    for x, y in ([0, 2], [1, 1], [2, 0]):
        if scores[a][x] > 0 and scores[b][y] > 0:
            scores[a][x] -= 1
            scores[b][y] -= 1
            dfs(depth+1)
            scores[a][x] += 1
            scores[b][y] += 1


num_cases = list(combinations(range(6), 2))
answer = []
for _ in range(4):
    input_list = list(map(int, input().split()))
    scores = [input_list[i:i+3] for i in range(0, 16, 3)]
    result = 0
    dfs(0)
    answer.append(result)

print(*answer)

고찰

모든 팀이 다른 팀과 1경기씩 한다는 것으로 백트래킹 방식이라는 것을 알아야되고 단순히 숫자로만 할 경우 다른 팀이 중복하여 경기할 수 있으므로 숫자로만 할 경우 에러가 생긴다.
가장 중요한 코드는 dfs안에 있는 for문으로 홈 팀을 기준으로 승 무 패를 순서대로 하여 숫자를 빼주고 아닐경우에는 그 다음 순서로 넘어간다.
숫자를 빼준후에 재귀를 하는데 조건을 만족하지 못하면 종료되어 +1을 하여 원상복구 한다.
마지막에 출력해보면 scores는 원래의 상황 그대로 된다. depth가 15일때 for-else문을 썼는데 런타임 에러가 났다. break문에서 나온후 return 을 빼먹어서 계속 걸렸다. 백트래킹을 구현하기가 힘들어 좀더 연습해봐야겠다. *answer부분도 유용하게 써야겠다.