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

문제 링크 : https://www.acmicpc.net/problem/6987

6987번: 월드컵

 

브루트포스, 백트래킹 문제이다.

나는 연산자 끼워넣기랑 유사하게 풀었다.

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

14888번: 연산자 끼워넣기

 

연산지 끼워넣기에는 사용가능한 연산자 개수가 정해져있다.

이문제도 비슷한데 승패무의 개수가 정해져있다.

 

그래서 A나라 부터 결과를 다른 나라와 맞춰보면서 진행한다.

만약 마지막 나라까지 도달했다면 끝내면 된다.

마지막 나라의 경우 다른 나라에 의해서 다 결정되기 때문에 보지 않아도 된다.

 

각 나라와 맞춰보는 과정은 아래와 같다.

만약 A나라가 1승 4무 0패 라면

처음에 B나라와 이겼다고 체크한다. 이때 A나라는 이겼으므로 승수를 -1해주고 B나라는 진 것이므로 B나라의 패수를-1을 해준다.

그리고 다음 결과로 진행한다.

끝까지 진행하고 다시 해당 시점으로 돌아왔을 때 C나라와 겨뤄본다. 이런식으로 브루트포스와 백트래킹을 이용했다.

 

만약 진행하다가 상대 결과 값이 0인데 빼려고 하는 경우는 불가능한 경우이므로 해당 경우는 지나간다.

 

def solv():
    global board
    input_data = list(map(int, input().split()))
    if 6 in input_data:
        return 0
    board = []
    for idx in range(0,18,3):
        board.append(input_data[idx:idx+3])

    if go(0,1):
        return 1
    else:
        return 0

def go(now, target,):
    if target == 6:
        now += 1
        target = now + 1
    if now == 5:
        return True

    for idx in range(3):
        if board[now][idx] > 0:
            if idx == 0:
                target_idx = 2
            elif idx == 1:
                target_idx = 1
            else:
                target_idx = 0
            if board[target][target_idx] > 0:
                board[now][idx] -= 1
                board[target][target_idx] -= 1

                if go(now, target+1, ):
                    return True

                board[now][idx] += 1
                board[target][target_idx] += 1
    return False

answer = []
for _ in range(4):
    answer.append(solv())

print(*answer)