[백준] 17281번 : ⚾

17281번: ⚾

완전탐색과 구현 문제의 조합입니다.

타순을 정한다. ( 모든 타순의 경우의 수를 구한다 )

1. 타순을 구하는 방법
   1. 순서가 있는 탐색임으로 깊이우선탐색으로 순열을 만든다.
   2. 1번 선수는 반드시 4번타자로 정해져 있으므로 4번 타자가 1번 선수가 아닌상황은 제외한다.
2. 구현법
   1. 이닝이 시작되고 타순을 돌린다.
   2. 각각의 선수에대하여 안타, 2루타, 3루타, 홈런, 아웃을 구현한다.
      1. 안타
         1. b[0], b[1] 각각 b[1], b[2]로 옮긴다.
         2. b[0]은 1이 된다.
         3. b[2]가 1일경우 점수를 획득한다.
      2. 2루타
         1. b[0], b[1] 각각 b[2]와 b[3]으로 옮긴다.
         2. b[1]은 1이된다.
         3. b[1], b[2]가 2일 경우 점수를 획득한다.
   3. 3아웃이 되면 베이스에 있는 값들을 모두 초기화 한다. 이닝을 하나 증가시킨다.
   4. 이닝이 N까지 도달되면 게임을 종료한다.

N = int(input())

table = [[0 for _ in range(10)] for _ in range(N+1)]
for i in range(1, N+1):
    temp = list(map(int, input().split()))

    for j in range(1, 10):
        table[i][j] = temp[j-1]
def dfs(player):
    if len(player) == 4:
        if player[3] != 1: # 4번 타자가 1번이 아닌경우
            return 0

    if len(player) == 9: # 플레이어 9명을 다 뽑은경우
        start = 0
        ining = 1
        score = 0
        while N+1 > ining:
            out, b1, b2, b3 = 0, 0, 0, 0
            while 3 > out:
                p = player[start]
                if table[ining][p] == 0: # 아웃인경우
                    out += 1
                elif table[ining][p] == 1: # 안타인경우
                    score += b3
                    b3 = b2
                    b2 = b1
                    b1 = 1
                elif table[ining][p] == 2: # 2루타인경우
                    score += b2
                    score += b3
                    b3 = b1
                    b2 = 1
                    b1 = 0
                elif table[ining][p] == 3: # 3루타인경우
                    score += b1
                    score += b2
                    score += b3
                    b1 = 0
                    b2 = 0
                    b3 = 1
                elif table[ining][p] == 4: # 홈런인경우
                    score += b1
                    score += b2
                    score += b3
                    score += 1
                    b1 = 0
                    b2 = 0
                    b3 = 0

                start += 1
                start %= 9

            ining += 1

        return score

    maxscore = 0
    for i in range(1, 10): # 순열임으로 1, 10 까지 모두 탐색한다.
        if i not in player:
            player.append(i)
            maxscore = max(maxscore, dfs(player))
            player.pop()

    return maxscore

print(dfs([]))