[BOJ] 15997 승부예측(카카오 코드 페스티벌 2018 A)

문제

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

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

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

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

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

입력

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

출력

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

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

[출처: 백준 온라인 저지]

풀이

카카오 코드 페스티벌 문제는 여러번 풀어봤지만 풀 때마다 어려운 것 같다. 그나마 A 문제여서 도전해봤는데, 이 문제는 비교적 쉬워서 풀만했던 것 같다. 4개의 팀이 모든 경우의 수에 다음 라운드로 진출할 수 있는 확률을 구해야하기 때문에, 브루트포스는 불가피 해 보였다. 다행히 팀도 4팀이고 경기가 6경기이기 때문에 브루트포스로 풀어도 버틸만 할 것 같았다. 대략 생각했던 로직은 6경기에 대하여 승리, 무승부, 패배 이 세가지 경우를 두고 모든 경우의 수를 possibility 배열에 product 모듈을 사용하여 저장한다(각 경기는 독립적이기 때문에 product 사용하여 중복 허용). 그 다음 확률 p를 1로 선언하였고(아직 아무 경기도 치루지 않은 상태이기 때문에 1), 각 경기 결과에 따라 그에 상응하는 확률을 곱해주어 6경기를 다 치루고 난 후 그 표본점에 대한 값인 p를 구할 수 있었다.

이 표본점에서 올라가는 두 팀을 구해야하는데, 문제는 동률이 나올 수도 있다는 점이었다. 먼저 score배열에서 가장 큰 값을 구했다. 그 다음 score 배열을 스캔하며 만약  인덱스 i에 해당하는 팀이 max_s의 값을 할당하고 있다면, 그 팀을 winner배열 안에 넣어준다. 그러나 여기서 최대값을 가지는 요소가 여러 개면(len(winner) != 1), 문제에서 제시했듯이 동률일 경우 공평하게 추첨으로 정한다고 했으니 올라 갈 수 있는 팀은 2팀이기 때문에 p에다가 (2/len(winner)만큼 곱해준 값을 동률인 팀에게 배분해야 한다.

이 과정을 거치면 두 번째로 올라가는 팀을 구할 필요가 없기 때문에 continue를 해주고, 만약 최대 승점을 가지고 있는 팀이 하나라면, 두 번째로 올라가는 팀을 구해야 한다. 여기서 최대값을 가지는 winner[0] 요소를 삭제해줘야 하는데, 이 때문에 딕셔너리 자료구조를 선언하였다. 나는 score의 인덱스로 다음 라운드로 올라갈 팀에 접근하고 싶은데, 만약 winner[0]을 삭제하는 연산을 진행하면 인덱스가 망가지기 때문이다. 그래서 딕셔너리 안에 각 팀의 인덱스를 key값으로, 승점을 value로 선언하였다. winner[0] 요소를 삭제하고 난후, 첫 번째 우승팀을 탐색했을 때랑 비슷한 원리로 구하면 된다. 여기서 다른 점은 이제 올라갈 팀이 1자리 밖에 안남았기 때문에 p*(1/len(second))를 해줬다는 것 뿐이다.

이 모든 과정을 지나고 나면 total_pos 배열 안에 각 팀이 올라갈 확률이 저장된다.

import sys
from itertools import product
input = lambda: sys.stdin.readline().rstrip()
name = input().split()
dic_name = {}
for i in range(len(name)):
  dic_name[name[i]] = i
game = [input().split() for _ in range(6)]
win_draw_lose = [2, 3, 4]
possibility = list(product(win_draw_lose, repeat = 6))
total_pos = [0] * 4
for pos in possibility:
  score = [0] * 4
  p = 1
  for i in range(len(pos)):
    if pos[i] == 2:
      score[dic_name[game[i][0]]] += 3
    elif pos[i] == 3:
      score[dic_name[game[i][0]]] += 1
      score[dic_name[game[i][1]]] += 1
    else:
      score[dic_name[game[i][1]]] += 3
    p *= float(game[i][pos[i]])
  dic_score = {}
  for i in range(len(score)):
    dic_score[i] = score[i]
  max_s = max(dic_score.values())
  winner = []
  for i in dic_score.keys():
    if dic_score[i] == max_s:
      winner.append(i)
  if len(winner) != 1:
    for w in winner:
      total_pos[w] += p*(2/len(winner))
    continue
  else:
    total_pos[winner[0]] += p
    del dic_score[winner[0]]
    max_s = max(dic_score.values())
    second = []
    for i in dic_score.keys():
      if dic_score[i] == max_s:
        second.append(i)
    if len(second) == 1:
      total_pos[second[0]] += p
    else:
      for s in second:
        total_pos[s] += p*(1/len(second))
for i in range(4):
  print(total_pos[i])

느낀 점

브루트포스 문제가 나오면 나는 itertools 패키지 안의 모듈을 사용하려는 경향이 있다. 일어날 수 있는 모든 경우의 수를 저장한 후에 하나씩 스캔하며 탐색하는 것이다. 또한 다음 라운드로 진출하는 두 팀을 탐색하는 부분을 조금 더 깔끔하게 구현할 수 있는게 아닌가 아쉬움이 남았다.