[BOJ] 6987: 월드컵 (Python)

문제 링크

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

풀이 전략

Backtracking

모든 경우를 다 따져보는 백트래킹 문제이다.

전체 경기는 아래와 같이 총 15번 진행된다.

• A vs B C D E F
• B vs C D E F
• C vs D E F
• D vs E F
• E vs F

또, 각 경기는 3가지 경우가 존재한다.

• Team 1 승리, Team 2 패배
• Team 1 비김, Team 2 비김
• Team 1 패배, Team 2 승리

모든 경기는 승무패의 개수가 정해져 있다. 따라서 1번째 경기부터 15번째 경기까지 조합을 미리 전부 구해두고, dfs를 돌리며 승무패를 1씩 빼가며 15번째 경기에 도달했을 때 전체 승무패의 합계가 0이 되는게 가능한지 구한다.

구현

from itertools import combinations

# 백트래킹
def dfs(depth):
    global cnt
    
    # 15번째 경기에 도달했을 때
    if depth == 15:
        cnt = 1
        for sub in res:
            # 전체 승무패의 합계가 0이 아니면
            if sub.count(0) != 3:
                cnt = 0
                break
        return
    
    # 전체 경기 15번의 조합
    g1, g2 = games[depth]
    # 각 경기의 승무패
    for x, y in ((0,2), (1,1), (2,0)):
        if res[g1][x] > 0 and res[g2][y] > 0:
            res[g1][x] -= 1
            res[g2][y] -= 1
            dfs(depth+1)
            res[g1][x] += 1
            res[g2][y] += 1

if __name__ == "__main__":
    answers = []
    games = list(combinations(range(6), 2))

    for _ in range(4):
        tmp = list(map(int, input().split()))
        res = [tmp[i:i+3] for i in range(0, 16, 3)]
        cnt = 0
        dfs(0)
        answers.append(cnt)
        
    print(*answers)

삽질

처음에는 총 승무패 수만 잘 맞추면 될 것 같아서 각 팀당 승무패 수를 wld 리스트에 저장해 총 경기 수와 일치하는지 비교하고, 무승부만 따로 draw_stack 변수에 기록해 한 팀만 무승부가 2회 있는 식의 경우를 제거하고자 했다.

하지만 간단히 생각해보아도 반례가 너무 많았고, 백트래킹을 통해 모든 경우를 다 따져보는 dfs를 구현한 후 가지치기를 적절하게 하면 될 것 같다고 생각을 했다.

if __name__ == "__main__":
  answers = []
  for _ in range(4):
      res = list(map(int, input().split()))
      
      # 승무패를 기록할 list
      wld = [0, 0, 0]
      draw_stack = 0
      for i in range(0, 18, 3):
      	  # 승리한 경우
          if (win:=res[i])>0:
              wld[0]+= win
          # 비긴 경우, draw_stack으로 따로 관리
          if (draw:=res[i+1])>0:
              wld[1] += draw
              if draw_stack <=0:
                  draw_stack+=draw
              else:
                  draw_stack-=draw
          # 패배한 경우
          if (lose:=res[i+2])>0:
              wld[2] += lose
		  # 한 팀당 경기가 5번이 아니면 오류
          if win+draw+lose!=5:
              break
      
      # 총 경기수가 30이고, 비긴 아다리가 맞으면 정답
      if wld[0]==wld[2] and sum(wld)==30 and draw_stack == 0:
          answers.append(1)
      else:
          answers.append(0)

  for answer in answers:
      print(answer, end = ' ')