백준 - 6987 월드컵

💡문제 분석 요약

• 각 나라의 승패 횟수가 주어졌을때 해당 예제가 가능한지 불가능하지 판별해야함

💡알고리즘 설계

[처음]

• 팀의 승,무,패 모든 경우를 고르는 방식으로 진행(DFS)
  [이후]
• 백트래킹
• 6개의 국가가 있고, 총 18번의 경기를 한다.
• 승, 무, 패의 결과가 있으며, 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0
• 입력은 네 줄로 들어오며, 각 줄에 대해 가능한 결과 1, 불가능한 결과 0 을출력하는 문제이다

💡변경한 코드

• 실패를 계속 해서,, 다른 사람의 소스를 옮겨봤다.

from sys import stdin
from itertools import combinations as cb


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

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


answer = []
game = list(cb(range(6), 2))
# 백트래킹
for _ in range(4):
    data = list(map(int, stdin.readline().split()))
    res = [data[i:i + 3] for i in range(0, 16, 3)]
    ans = 0
    solution(0)
    answer.append(ans)

print(*answer)

💡시간복잡도

💡 틀린 이유

DFS 로 하려고 하니까 시간초과 + 메모리 초과 오류가 발생했다.
백트래킹으로 다시 풀어봐야할 것 같다.

💡 틀린 부분 수정 or 다른 풀이

DFS 방식에서 백트래킹 방식으로 변경

💡 느낀점 or 기억할정보

DFS와 백트래킹의 차이를 잡기가 조금 어려운 것 같다.
조금 더 개념에 익숙해진 후에 소스 적용을 더 해봐야할 것 같다.