[백준(BOJ)] #15997- 승부 예측 (파이썬, PyPy3)

문제

 

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

15997번: 승부 예측

 

---

문제 풀이

DFS 알고리즘으로 완전 탐색을 하여 해결하였습니다. 

2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

문제 갈피가 잡히지 않아서 다음 블로그 글을 참고하여 구현했습니다.

https://qrlagusdn.tistory.com/78

[맛있는물회] <백준 알고리즘> 15997번 "승부 예측"

 

모든 경우의 수에 따른 확률, 승점

모든 경기는 승, 무승부, 패로 결과가 나뉘고 경기는 총 6경기이므로 3^6 가지의 경우의 수로 나뉘고, 이 크기는 완전탐색으로 충분히 커버할 수 있습니다. 

DFS 알고리즘과 백트래킹을 사용하여 6번의 경기에서 일어날 수 있는 모든 확률에 대한 경우의 수를 구해줍니다.

KOREA CCC BBB AAA
KOREA CCC 1.0 0.0 0.0
AAA BBB 0.428 0.144 0.428
AAA KOREA 0.0 0.0 1.0
CCC BBB 0.0 0.0 1.0
KOREA BBB 1.0 0.0 0.0
CCC AAA 0.0 0.0 1.0

위와 같은 입력을 예로 들면, 위에서 부터 차례대로 KOREA 승, AAA 승, KOREA 승, BBB 승, KOREA 승, AAA 승 이렇게 한 가지 경우가 포함되어 있습니다.

 

맨 처음 KOREA가 이길 확률은 1.0이므로 무조건 이기게 되고, 다름 경기는 AAA가 이길 확률이 0.428이므로 누적 확률을 구하면 0.428(1.0 * 0.428), 다음 경기는 KOREA가 이길 확률이 1.0이므로 0.428(1.0 * 0.428)... 이렇게 누적 확률을 계산하면  KOREA 승, AAA 승, KOREA 승, BBB 승, KOREA 승, AAA 승에 대한 확률은 0.428이 됩니다.

 

이렇게 확률을 구하는 과정에서 승점을 구하는 작업도 해줘야 합니다.

 

6번의 경기를 모두 마친 경우

6번의 경기가 끝나고 누적 확률과 승점을 구했으면 동점팀 상황을 고려하여 최종적으로 본선에 진출할 두 팀을 구합니다. 

 

1) 4팀의 승점이 모두 같은 경우

• 4팀 중 2팀만 본선 진출가능하므로 * 1/2(2/4)

 

2) 1등이 정해져있고, 나머지 팀의 승점이 같은 경우

• 나머지 3팀 중 1팀만 본선 진출 가능 * 1/3

 

3) 4등이 정해져있고, 나머지 팀의 승점이 같은 경우

• 나머지 3팀 중 2팀만 본선 진출 가능 * 2/3

 

4) 1등과 4등이 정해져있고, 나머지 팀의 승점이 같은 경우

• 나머지 2팀 중 1팀만 본선 진출가능 * 1/2

 

5) 그 외

• 진출 가능

 

---

구현

코드

import sys
input = sys.stdin.readline

def dfs(cnt, score_dict, p):
    # 6경기 모두 완료 한 경우
    if cnt == 6:
    	# 리스트로 변환후 승점 내림차순으로 정렬
        score_dict = sorted(list(score_dict.items()),
                            key=lambda k: k[1], reverse=True)

        # 1 = 2 = 3 = 4 / 4명 중 2명
        if score_dict[0][1] == score_dict[1][1] == score_dict[2][1] == score_dict[3][1]:
            answer_dict[score_dict[0][0]] += p*1/2
            answer_dict[score_dict[1][0]] += p*1/2
            answer_dict[score_dict[2][0]] += p*1/2
            answer_dict[score_dict[3][0]] += p*1/2
            return

        # 1 > 2 = 3 = 4 / 3명 중 1명
        elif score_dict[0][1] > score_dict[1][1] == score_dict[2][1] == score_dict[3][1]:
            answer_dict[score_dict[0][0]] += p
            answer_dict[score_dict[1][0]] += p*1/3
            answer_dict[score_dict[2][0]] += p*1/3
            answer_dict[score_dict[3][0]] += p*1/3
            return

        # 1 = 2 = 3 > 4 / 3명 중 2명
        elif score_dict[0][1] == score_dict[1][1] == score_dict[2][1]:
            answer_dict[score_dict[0][0]] += p*(2/3)
            answer_dict[score_dict[1][0]] += p*(2/3)
            answer_dict[score_dict[2][0]] += p*(2/3)
            answer_dict[score_dict[3][0]] += p*0.0
            return

        # 1 > 2 = 3 > 4 / 2명 중 1명
        elif score_dict[0][1] > score_dict[1][1] == score_dict[2][1]:
            answer_dict[score_dict[0][0]] += p
            answer_dict[score_dict[1][0]] += p*0.5
            answer_dict[score_dict[2][0]] += p*0.5
            answer_dict[score_dict[3][0]] += p*0.0
            return

        # 그 외
        else:
            answer_dict[score_dict[0][0]] += p
            answer_dict[score_dict[1][0]] += p
            answer_dict[score_dict[2][0]] += p*0.0
            answer_dict[score_dict[3][0]] += p*0.0
            return

    # A 승
    # 누적 승점
    score_dict[match_list[cnt][0]] += 3
    # 누적 확률
    dfs(cnt+1, score_dict, p*float(match_list[cnt][2]))
    # 백트래킹
    score_dict[match_list[cnt][0]] -= 3

    # 비김
    score_dict[match_list[cnt][0]] += 1
    score_dict[match_list[cnt][1]] += 1
    dfs(cnt+1, score_dict, p*float(match_list[cnt][3]))
    score_dict[match_list[cnt][0]] -= 1
    score_dict[match_list[cnt][1]] -= 1

    # A 패
    score_dict[match_list[cnt][1]] += 3
    dfs(cnt+1, score_dict, p*float(match_list[cnt][4]))
    score_dict[match_list[cnt][1]] -= 3


if __name__ == "__main__":
    nation1, nation2, nation3, nation4 = map(str, input().split())
    match_list = [list(input().split()) for _ in range(6)]

    score_dict = {nation1: 0, nation2: 0, nation3: 0, nation4: 0}
    answer_dict = {nation1: 0.0, nation2: 0.0, nation3: 0.0,
                   nation4: 0.0}

    dfs(0, score_dict, 1)

    for key in score_dict:
        print(answer_dict[key])

결과