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

탐색문제가 아직 어색한 나에겐 상당히 어려웠다..,.

역시 카카오 코딩 페스티벌 본선 문제인 듯 싶었다. 그런데 본선진출자 64명 중 제출자 62명 전원 정답....ㅎㅎ

백준 정답률은 10프로던데,,, 

역시는 역신갑다 ㅎㅎ

 

어쨌든 진짜 완전탐색에 대해 (재귀함수) 정말 많이 익숙해져야한다고 느꼈다. 아직 DFS 부분이 바로바로 나오는게 아니라서 정말 많은 문제를 풀어봐야한다고 생각한다.

화이팅화이팅!

 

문제 조건

---

심심했던 무지와 콘은 TV를 보다가, 대한민국 선수단이 실시간으로 출전하고 있는 경기를 보게 되었다.

지금 보고 있는 경기는 조별리그가 진행 중인데, 대한민국이 속한 조는 총 4개 국가가 참가하여 경기가 진행되고 있다.

조별리그의 규칙은 다음과 같다.

• 4개의 팀이 조별리그를 진행한다.
• 한 팀은 자신을 제외한 모든 상대방과 한 번씩, 총 3번의 경기를 치른다.
• 경기의 승자는 승점 3점을 받고 비기는 경우 서로 승점 1점을 받는다. 지는 경우에는 승점을 받지 않는다.
• 조별리그를 모두 치른 후 승점 순으로 순위를 정하는데 승점이 같을 시에는 추첨으로 순위를 정하며, 추첨은 공평하게 진행된다. 순위를 정한 후 상위 2팀은 다음 라운드로 진출한다.

전문가들은 조별 리그의 6경기 전체에 대해서 어떤 팀이 승리할 확률, 비길 확률, 패배할 확률을 예측하였다. 무지와 콘은 모든 경기가 독립적으로 진행되었을 때 (어떠한 경기의 결과가 다른 경기의 결과에 영향을 주지 않음), 전문가들의 예상대로 진행된다면 각 팀이 조별리그를 통과하여 다음 라운드로 진출할 확률이 궁금해졌다. 하지만 무지와 콘은 직접 확률을 계산하지 못했고, 여러분들에게 도움을 요청하였다. 무지와 콘을 도와 이 문제를 해결해보자!

 

Input

---

첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다.
두 번째 줄부터 일곱 번째 줄까지는 A B W D L 순으로 주어지는데, 전문가들의 예측에 따르면 A와 B가 경기를 진행했을 때 A가 승리할 확률은 W, 비길 확률은 D, 질 확률은 L이라는 의미이다.
A, B는 각각 첫 번째 줄에 있는 국가명 중 하나이고, A와 B가 같은 경우는 주어지지 않는다. 또한 W, D, L은 최대 소수점 세 자리까지 주어지며, W + D + L = 1이 보장된다.

 

Output

---

i 번째 줄에, i 번째로 입력받은 국가가 다음 라운드에 진출할 확률을 출력한다.

출력한 결과와 실제 답을 비교하였을 때의 상대 오차 또는 절대 오차가 10-6 이하인 경우에만 정답으로 인정한다.

 

생각한 아이디어

---

처음에는 왜 그렇게 생각한지 모르겠는데 단순하게 확률을 입력받고 승점과 곱한다음에 Sorting을 했다.

그렇게 했더니 첫번째 케이스는 맞게 나오길래 제대로 접근한 줄 알았는데 그게 아니었다.

 

현재 6번의 경기가 치뤄진다. 따라서 3^6개의 케이스가 발생한다. 

그렇게 큰 숫자가 아니기 때문에 완전탐색으로 풀 수있다.

즉, 3^6 번의 케이스를 모두 계산한 다음에 그에 해당하는 확률을 계산해서 나타내는 것이다.

 

확률과 통계를 배웠는데도 좀 헷갈리는 부분이었다. ㅎㅎ

다시 말해서 이런 식으로 모든 케이스를 계산한다는 말이다.

 

먼저 승, 비김, 패배 이렇게 3가지 경우가 있다.

첫 번째 케이스는

Korea VS CCC -> Korea 승

AAA VS BBB -> AAA 승

AAA VS KOREA -> AAA승

CCC VS BBB -> CCC승

KOREA VS BBB -> Korea 승

CCC VS AAA -> CCC 승

이렇게 나온다면 확률 값을 쫙 계산해주어야 한다.

 

승리 할때마다 승리하는 팀에 승점 3점을 부여해주는 것도 잊지말아야 한다.

 

그렇게 3가지 케이스를 나누고 각각 DFS 재귀함수를 시행한다.

 

만약 입력된 6개의 경기를 다 치뤘다면 (idx == 6) 

승점 입력받은 리스트를 Sorting 해서 1등부터 4등까지 정렬한다.

계산하여 나온 확률값을 다시 4팀 중 2팀만 올라갈 수 있게 계산해준다.

 

먼저 4팀이 동점인 경우 (2/4)

3팀이 동점인 경우

-> 1 == 2 == 3 > 4 (2/3)

-> 1 > 2 == 3 == 4 (1/3)

2팀이 동점인 경우

-> 1 > 2 == 3 > 4 (1/2)

그리고 나머지의 경우에는 1등과 2등만 확률을 부여한다.

 

싹 다 계산해서 각각 나라에 나온 확률 값들이 정답!!

 

케이스 구분하는 부분이 꽤 번거로운 문제이다.

 

소스코드

#카카오 코드페스티벌 승부 예측 
#https://www.acmicpc.net/problem/15997
#브루트포스 알고리즘 공부하기
#DFS 다시 공부하기
#소팅하는 부분 다시 공부
#->

import sys

def dfs(cnt,scoreDic, P):
    if cnt == 6:#소팅하는부분
        sortDic = sorted(list(scoreDic.items()), key = lambda k : k[1], reverse = True)
        if sortDic[0][1] == sortDic[1][1] == sortDic[2][1] == sortDic[3][1]: #상위 4개가 똑같은경우 0.25, 0.25, 0.25. 0.25 4명동점
            ansDic[sortDic[0][0]] += P*1/2
            ansDic[sortDic[1][0]] += P*1/2
            ansDic[sortDic[2][0]] += P*1/2
            ansDic[sortDic[3][0]] += P*1/2
            return

        
        elif sortDic[0][1] > sortDic[1][1] == sortDic[2][1] == sortDic[3][1] :#2 3 4 등이 똑같을 수도 3명동점
            ansDic[sortDic[0][0]] += P
            ansDic[sortDic[1][0]] += P*1/3
            ansDic[sortDic[2][0]] += P*1/3
            ansDic[sortDic[3][0]] += P*1/3
            return

        #elif sortDic[0][1] == sortDic[1][1] == sortDic[2][1] > sortDic[3][1] :#상위 3개가 똑같은 경우 0.3333,0.3333,0.3333, 0 3명동점
        elif sortDic[0][1] == sortDic[1][1] == sortDic[2][1] :#상위 3개가 똑같은 경우 0.3333,0.3333,0.3333, 0 3명동점
            ansDic[sortDic[0][0]] += P*(2/3)
            ansDic[sortDic[1][0]] += P*(2/3)
            ansDic[sortDic[2][0]] += P*(2/3)
            ansDic[sortDic[3][0]] += P*0.0
            return

        #elif sortDic[0][1] > sortDic[1][1] == sortDic[2][1] > sortDic[3][1]:#2위 3위가 똑같은 경우 1, 0.5, 0.5, 0 2명동점

        elif sortDic[0][1] > sortDic[1][1] == sortDic[2][1] :#2위 3위가 똑같은 경우 1, 0.5, 0.5, 0 2명동점
            ansDic[sortDic[0][0]] += P
            ansDic[sortDic[1][0]] += P*0.5
            ansDic[sortDic[2][0]] += P*0.5
            ansDic[sortDic[3][0]] += P*0.0
            return

        else: #그 외는 1, 1, 0 ,0  
            # 1=2,3,4 / 1,2,3=4/ 1,2,3,4
            ansDic[sortDic[0][0]] += P
            ansDic[sortDic[1][0]] += P
            ansDic[sortDic[2][0]] += P*0.0
            ansDic[sortDic[3][0]] += P*0.0
            return

    
    #A가 이길 때
    scoreDic[stringList[cnt][0]] += 3 #A    

    dfs(cnt+1, scoreDic, P*float(stringList[cnt][2]))#dfs 파라미터에 scoreDic이 들어가는 이유를 제대로 알자!!
    
    scoreDic[stringList[cnt][0]] -= 3 #A

    #비길때
    scoreDic[stringList[cnt][0]] += 1 #A
    scoreDic[stringList[cnt][1]] += 1 #B

    dfs(cnt+1,scoreDic, P*float(stringList[cnt][3]))
    
    scoreDic[stringList[cnt][0]] -= 1 #A
    scoreDic[stringList[cnt][1]] -= 1 #B

    #A가 질 때
    scoreDic[stringList[cnt][1]] += 3 #B

    dfs(cnt+1,scoreDic, P*float(stringList[cnt][4]))
    
    scoreDic[stringList[cnt][1]] -= 3 #B


if __name__ == "__main__":
    name1, name2, name3, name4 = map(str,input().split())
    #나라이름 입력받기
    stringList = list()

    for i in range(6):
        string = list(map(str,input().split()))
        stringList.append(string)


    scoreDic = {name1:0,name2:0,name3:0,name4:0} 
    ansDic = {name1:0.0,name2:0.0,name3:0.0,name4:0.0} #본선진출 확률 대입할 리스트

    dfs(0, scoreDic, 1)

    for key in scoreDic:
        print(ansDic[key])

 

*파이썬 문법 정리

- 리스트 Sorting 하기

Sort() 라는 함수를 사용하면 바로바로 정렬이 되어버린다. 하지만 만약 리스트나 딕셔너리와 같이 여러개의 값들 중 특정값으로 정렬을 하고 싶은 경우에는 sorted와 같은 함수를 사용해야한다. 예를 들어 

sorted(student_tuples, key=lambda student: student[2])

이면 student_tuples 리스트의 [2]번째 값을 기준으로 하여 student_tuples 리스트를 정렬하는 것이다.

 

sortDic = sorted(list(scoreDic.items()), key = lambda k : k[1], reverse = True)

라고 적으면 scoreDic이라는 딕셔너리의 item을

 

딕셔너리와 리스트를 가지고 조작하는 부분이 좀 헷갈려서 몇 가지 테스트를 해봤다.

scoreDic = {1:5,2:3,3:4,4:5464} 

의 딕셔너리가 있다.

print(list(scoreDic.items()))            [(1, 5), (2, 3), (3, 4), (4, 5464)]

print(scoreDic)                          {1: 5, 2: 3, 3: 4, 4: 5464}

print(scoreDic.items())                dict_items([(1, 5), (2, 3), (3, 4), (4, 5464)])

sortDic = sorted(list(scoreDic.items()), key = lambda k : k[1], reverse = True)    [(4, 5464), (1, 5), (3, 4), (2, 3)]

 

이렇게 나온다!