[백준 6987번] 파이썬 - 월드컵

백준 6987 - 월드컵

시간 제한 1초, 메모리 제한 128MB

# 조건

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

• 네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다.
• 승, 무, 패의 수는 6보다 작거나 같은 자연수 또는 0이다.

출력

• 입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

# 접근 방법

• 처음에는 그리디로 접근하여 풀려고 하였다.
  • 전체 승 패의 수가 같고, 무승부의 경우 짝이 맞는지만 체크해주었는데 5승인 팀이 2팀, 5패인 팀이 2팀과 같이 불가능한 경우가 있었기에 틀렸습니다를 받았다.
• 따라서, 완전 탐색으로 접근하였다.
• 전체 경기수는 5+4+3+2+1 = 15개의 경기가 발생하고 각각의 경기에는 승, 무, 패가 존재한다.
• 15개의 경기를 조합으로 구해준 뒤, 승 무 패를 순회하며 현재 조합의 두 팀의 승무패를 1씩 빼며 15번째 경기에 도달하였을 때 승 무 패의 합계가 0이 되는지 체크해주었다.
• 입력받는 경기 정보를 0~5번 국가에 각각 0번은 승리, 1번은 무승부, 2번은 패배 횟수로 기록해준다.
  • [[5,0,0], [3,0,2] ...]
• (1, 2), (1, 3) .. (5, 6) 까지의 모든 경기에 대해 조합을 구한 뒤
  • DFS 함수 내부에서는 for i in [(0, 2), (1, 1), (2, 0)]을 순회한다.
  • 여기서 0은 승리, 1은 무승부, 2는 패배를 뜻한다.
• 만약 1번 국가과 2번 국가를 탐색 중이라면
  • 1번 국가의 0번 인덱스가 0이상이고, 2번 국가의 2번 인덱스가 0이상이라면 가능한 매치이므로
  • 각 인덱스 값을 -= 1을 해주고 dfs(idx+1)을 해주며 다음 경기를 살펴본다.
• return을 받은 후 다시 1번 국가의 0번을 += 1, 2번 국가의 2번 인덱스를 +=1을 해주며 가능한 모든 경우를 살펴보아야 한다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  

# idx는 현재 몇 번쨰 경기인지  
def dfs(idx):  
    global ans  
    # 마지막 경기라면 승 무 패의 합이 0이여야 됨  
    if idx == 15:  
        for i in group:  
            if not sum(i) == 0:  
                return  
        ans = 1  
        return  

    # 승 무 패를 순회하며 현재 두팀에서 가능한 결과가 있다면 재귀로 다음 경기 살펴보기  
    first = games[idx][0]  
    second = games[idx][1]  
    for one, two in [(0, 2), (1, 1), (2, 0)]:  
        if group[first][one] > 0 and group[second][two] > 0:  
            group[first][one] -= 1  
            group[second][two] -= 1  
            dfs(idx + 1)  
            group[first][one] += 1  
            group[second][two] += 1  

answer = []  
for _ in range(4):  
    ans = 0  
    result = [*map(int, input().split())]  
    group = []  
    # 각 국가의 승 무 패를 0, 1, 2번 인덱스에 할당해주기  
    for j in range(0, 18, 3):  
        group.append([result[j], result[j+1], result[j+2]])  
    # 발생할 수 있는 15경기의 조합을 미리 구해준다.  
    games = list(combinations(range(6), 2))  
    dfs(0)  
    answer.append(ans)  
print(*answer)

• 항상 백트래킹의 경우 재귀적인 부분을 어떻게 처리할지 생각해내는 것이 어려운 것 같다.
• 이번 문제의 경우 각 경기의 조합을 승 무 패를 재귀로 돌리는 과정과 하나라고 생각하여 아이디어 구현이 복잡해보여 시간이 오래 걸렸다.
• 함수 모듈화와 같이 필요한 각 부분을 따로따로 생각한 뒤, 합칠 수 있는 것을 찾는 것이 중요한 것 같다.