[백준 17281번] ⚾ (C/C++)

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

17281번: ⚾

---

야구 게임 문제는 큐와 백트래킹을 이용하여 문제를 풀 수 있습니다. 

백트래킹을 이용하여 타순의 모든 경우의 수를 구하고, 각 타순에 대한 게임 결과를 계산하면 됩니다. 

 

알고리즘의 기본 틀은 아래와 같습니다.

1. 타순의 각 경우의 수에 대해 게임을 진행한다. (단, 1번 타자를 제외한 permutation을 구한다.)
2. 타순의 4번 타자에 1번 선수를 넣는다.
3. 게임을 시작한다. 
   • 3-1) 이닝을 시작한다. (단, 모든 이닝이 끝난 경우 4번을 진행한다.)
   • 3-2) 각 타자가 얻는 결과에 따라 게임을 진행한다. 
     1. out이 아닌 경우, 결과에 따라 주자를 진루시킨다. 
     2. out인 경우, out을 증가시킨다.
   • 3-3) out이 3번 이상인 경우 3-1)번부터 시작한다. 
4. 게임을 종료한다.

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int s[50][9];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;

    for(int i = 0; i < n; i++)  
        for(int j = 0; j < 9; j++)
            cin >> s[i][j]; // 각 선수가 이닝에서 얻는 결과를 입력 받음.

    int np[8] = {1, 2, 3, 4, 5, 6, 7, 8};

    int ans = INT_MIN;
    do{
        deque<int> h; 
        for(int i = 0; i < 3; i++) h.push_back(np[i]);   // 타자 순서
        h.push_back(0); // 4번 타자에 1번 선수를 넣음
        for(int i = 3; i < 8; i++) h.push_back(np[i]);   

        int ining = 0, score = 0;
        while(ining < n){   // 게임 시작
            int out = 0;    // 현재 이닝에서의 out 횟수
            queue<int> base; for(int i = 0; i < 3; i++) base.push(0);   // base를 모두 0으로 채움

            while(out < 3){ // 3아웃이 발생할 때까지 이닝 진행
                int cur = h.front(); // 현재 타자
                h.pop_front(); h.push_back(cur);   // 현재 타자를 마지막 타자로 다시 넣음
                if(s[ining][cur] == 0) out++;   // 아웃인 경우
                else{   // 아웃이 아닌 경우
                    if(base.front() == 1) score++;  // 3루수 홈으로 진루
                    base.push(1); base.pop();   // 1루로 진루
                    for(int i = 0; i < s[ining][cur] - 1; i++){ // 나머지 진루
                        if(base.front() == 1) score++;
                        base.pop(); base.push(0);
                    }
                }
            }
            ining++;    // 이닝 증가
        }   // 게임 종료
        ans = max(ans, score);
    }while(next_permutation(np, np + 8));
    cout << ans;
}