[알고리즘] 월드컵 - 백트래킹

1. 문제

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

 

 

2. 풀이

[ 실패 풀이 코드 부분 ]

1. 한 국가당 무승부 + 승 + 패의 수가 5여야 한다

2. 무승부가 나온다면 무승부의 수는 짝수이면서, 최소 2개 국가가 무승부를 기록해야한다

3. 승 수 == 패 수

위의 3가지 조건만 있다고 간과하였습니다.

 

이 과정에서 질문 게시판을 보았고 내가 생각했던 반례보다 훨씬 더 많은 반례가 있다는 것을 알게되며, 백트래킹으로 풀어야 함을 알게됐습니다.

 

예를 들면,

1. 한팀이 5번 이기면 다른 팀들은 한번씩 필수로 져야한다

2. 한팀이 5번 패하면 다른 팀들은 한번씩 필수로 이겨야한다

-> 1번과 2번의 이유로 5승한팀이 2개 이상, 5패한 팀이 2개 이상이 있을 수 없다.

등등 반례가 무수히,,,

 

하지만, 어떤식으로 백트래킹을 접목해야할지 몰라서 질문 게시판을 더 참고했고, 본 내용을 조금 변형해서 풀게 됐습니다.

[ 제가 본 질문 게시판 : https://www.acmicpc.net/board/view/111381 ]

 

[ 성공 풀이 코드 부분 ]

1. 참고한 질문 게시판에서 저는 progess부분이 이해가 가면서도 제가 이해하기에는 조금 복잡하다고 느꼈습니다.

2. 결국 중복되지 않는 조합으로 6C2 개의 match가 성사 되니, 이를 matchup으로 좀 쉽게 볼 수 있다고 생각했습니다.

3. 이제 좀 기본적으로 볼 수 있는 백트래킹의 형태로 문제를 풀었습니다. ( 이해가 쉬워졌을거라 판단합니다 )

 

참고로 res[team1][i] > 0 and res[team2][2-i] > 0 조건문이 이해가 안될 수 있는데, 2차원 배열에서

0번째 인덱스 값은 승, 2번째 인덱스 값은 패의 수를 의미한다는 걸 알면 될거 같습니다.

 

3. 코드

실패 코드 - 완탐을 통한 코드

ans = []

res = [
    list(map(int,input().split()))
    for _ in range(4)
]

for six_country in res:
    tot_win, tot_lose, tot_tie = 0,0,0
    tmp_win, tmp_lose, tmp_tie = 0,0,0
    tie_country = 0
    flag = False

    for i in range(18):
        if i % 3 == 0: # 승
            tmp_win += six_country[i]
            tot_win += six_country[i]

        elif i % 3 == 1: # 무승부
            if six_country[i] != 0:
                tmp_tie += six_country[i]
                tot_tie += six_country[i]
                tie_country += 1

        elif i % 3 == 2: # 패
            tmp_lose += six_country[i]
            tot_lose += six_country[i]

            # flag 
            if tmp_lose + tmp_tie + tmp_win != 5:
                ans.append(0)
                flag = True
                break

            tmp_win, tmp_lose, tmp_tie = 0,0,0

    if flag:
        continue
    
    if tot_lose != tot_win:
        ans.append(0)
        continue
    
    if tot_tie % 2 == 1 or (tot_tie != 0 and tie_country == 1):
        ans.append(0)
        continue

    tmp_win, tmp_lose, tmp_tie,tie_country = 0,0,0,0
    ans.append(1)

print(*ans)

 

성공 코드 - 백트래킹

arr = [
    list(map(int,input().split()))
    for _ in range(4)
]

ans = []

matchup = [
    (0,1),(0,2),(0,3),(0,4),(0,5),
    (1,2),(1,3),(1,4),(1,5),
    (2,3),(2,4),(2,5),
    (3,4),(3,5),
    (4,5),
]

def choose(matchup_idx):

    global cnt

    if matchup_idx == 15:
        cnt = 1
        return
    
    team1, team2 = matchup[matchup_idx]
    
    for i in range(3):
        if res[team1][i] > 0 and res[team2][2-i] > 0:
            res[team1][i] -= 1
            res[team2][2-i] -= 1

            choose(matchup_idx+1)

            res[team1][i] += 1
            res[team2][2-i] += 1


for i in arr:

    res = [
        i[j * 3 : (j+1) * 3]
        for j in range(6)
    ]

    cnt = 0

    for j in range(6):
        if sum(res[j]) != 5:
            break
    else:
        choose(0)
    
    ans.append(cnt)

print(*ans)