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

https://www.acmicpc.net/problem/6987

코드

from itertools import combinations


def bt(idx):
    global ans, match_results
    if idx == 15:
        ans = 1
        for nation in match_results:
            if nation.count(0) != 3:
                ans = 0
                break
        return
    home, away = matchs[idx]
    for h, w in [(0, 2), (1, 1), (2, 0)]:   # home 이김, 비김, home 짐
        if match_results[home][h] > 0 and match_results[away][w] > 0:
            match_results[home][h] -= 1
            match_results[away][w] -= 1
            bt(idx+1)
            match_results[home][h] += 1
            match_results[away][w] += 1


answer = []
matchs = list(combinations(range(6), 2))
for i in range(4):
    line = list(map(int, input().split()))
    match_results = [line[i*3:i*3+3] for i in range(6)]
    ans = 0
    bt(0)
    answer.append(ans)

print(*answer)

 

참여 국가의 수가 6개로 정해져있어서 가능한 모든 경기 결과를 다 해보면 되는 문제였다. 이때  백트래킹을 이용해서 확실하게 불가능한 경우의 수는 가지치기를 해내야 한다.

 

우선 가능한 경기의 경우를 만들기 위해 조합(combination)을 사용했다.

matchs = list(combinations(range(6), 2))

이렇게 만들면 `matchs`는 `[(0, 1), (0, 2), (0, 3), ..., (3, 4), (3, 5), (4, 5)]`가 된다. 길이는 15.

(0, 1)은 0번 국가와 1번 국가의 경기를 말한다.

 

그리고 문제를 보면 한 줄에 모든 경기 결과가 다 들어오기 때문에 입력 한 줄씩 이 결과가 가능한 결과인지 확인해주면 된다. 경기 결과는 각 국가별로 구분하기 위해 3개씩 잘라서 `match_results`라는 2차원 배열로 저장해둔다. 

 

이제 `bt()` 함수를 재귀적으로 실행하며 이 각각의 경기에서 가능한 모든 경우의 수를 다 해보면 된다. 예를 들어, 0번 국가와 1번 국가의 경기라면

1. 0번 국가가 이기는 경우 (`(0, 2)`)

2. 비기는 경우 (`(1, 1)`)

3. 0번 국가가 지는 경우 (`(2, 0)`)

home, away = matchs[idx]
for h, w in [(0, 2), (1, 1), (2, 0)]:   # home 이김, 비김, home 짐
    if match_results[home][h] > 0 and match_results[away][w] > 0:
        match_results[home][h] -= 1
        match_results[away][w] -= 1
        bt(idx+1)
        match_results[home][h] += 1
        match_results[away][w] += 1

각 경우마다 경기 결과를 저장해놓은 `match_results`에서 해당하는 경기 결과 횟수를 1씩 빼준다. 만약 이 때 match_results[a][b]가 이미 0인데 또 빼려고 한다면 안되는 경우인거다. 이런 경우에는 가지치기를 해줘야 불필요한 함수 실행을 막을 수 있다. (백트래킹)

 

이렇게 재귀실행을 해서 `idx==15`까지 간다면 이제 match_results에 남은 경기 횟수가 있는지 확인하고 없다면 1, 있다면 0을 ans에 저장하면 된다. 남은 경기 횟수가 있다는 것은 6개의 국가가 각각 한 번씩 경기를 한 것보다 경기 결과에 표기된 것이 많다는 말이므로 불가능한 케이스에 해당한다.