백준 - 17281 야구(Java)

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

17281번: ⚾

 

구현 문제입니다.

 

규칙은 일반 야구와 동일합니다.

순열을 사용하여 9명의 타자 순서를 만들어 점수를 계산하는 완전탐색으로 하면 됩니다.

단, 각 이닝의 첫 번째 입력이 4번 타자가 되야하기 때문에 

첫 번째 입력을 4번으로 고정한 뒤, 순열에서 4번 타자의 위치가 바뀌지 않도록 하면 됩니다.

private static void swap(int[] inning, int depth, int i) {
    if (depth == ACE || i == ACE) return; // 4번 타자의 위치가 바뀌지 않도록 함

    int tmp = inning[depth];
    inning[depth] = inning[i];
    inning[i] = tmp;
}

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Main {
    private static final String SEPARATOR = " ";
    private static final int PLAYERS = 9;
    private static final int FIRST = 0; // 타자는 0번부터 시작
    private static final int ACE = 3; // 4번 타자
    private static final int MAX_OUT_COUNT = 3; // 이닝이 종료되는 아웃 카운트
    private static final int BASE_COUNT = 3; // 1루, 2루, 3루 수

    private static Set<String> set;

    private static int n, answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());

        List<int[]> playerAbility = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            stz = new StringTokenizer(br.readLine(), SEPARATOR);
            playerAbility.add(new int[PLAYERS]);

            for (int j = 0; j < PLAYERS; j++) {
                int ability = Integer.parseInt(stz.nextToken());
                playerAbility.get(i)[j] = ability;
            }
        }

        // 순서 설정 -> 첫 번째가 4번 타자가 되도록 위치를 바꿈
        int[] lineUp = new int[PLAYERS];
        for(int i=0; i<PLAYERS; i++) lineUp[i] = i;
        lineUp[FIRST] = ACE;
        lineUp[ACE] = FIRST;

        set = new HashSet<>();
        permutation(lineUp, 0, playerAbility);

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static void permutation(int[] lineUp, int depth, List<int[]> playerAbility) {
        if (depth == PLAYERS) {

            // 중복 연산 제거
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<PLAYERS; i++) sb.append(lineUp[i]);
            if(set.contains(sb.toString())) return;
            set.add(sb.toString());

            // 점수 계산
            int score = doBaseBallGame(playerAbility, lineUp);
            answer = Math.max(answer, score);
            return;
        }

        for (int i = depth; i < PLAYERS; i++) {
            swap(lineUp, depth, i);
            permutation(lineUp, depth + 1, playerAbility);
            swap(lineUp, depth, i);
        }
    }

    private static void swap(int[] inning, int depth, int i) {
        if (depth == ACE || i == ACE) return; // 4번 타자의 위치가 바뀌지 않도록 함

        int tmp = inning[depth];
        inning[depth] = inning[i];
        inning[i] = tmp;
    }

    private static int doBaseBallGame(List<int[]> playerAbility, int[] lineUp) {
        int totalScore = 0;
        int atBat = FIRST;
        boolean[] bases = new boolean[BASE_COUNT];

        for (int[] inning : playerAbility) {
            Arrays.fill(bases, false);
            int outCount = 0;

            while (outCount < MAX_OUT_COUNT) {
                int hitter = inning[lineUp[atBat++]]; // 해당 이닝과 순서를 지닌 타자의 결과

                if (hitter == 0) { // 아웃
                    outCount++;
                } else if (hitter == 1) { // 안타
                    if (bases[2]) {
                        totalScore++;
                        bases[2] = false;
                    }
                    if (bases[1]) { // 2루 -> 3루
                        bases[2] = true;
                        bases[1] = false;
                    }
                    if (bases[0]) { // 1루 -> 2루
                        bases[1] = true;
                    }
                    bases[0] = true;
                } else if (hitter == 2) { // 2루타
                    for (int j = BASE_COUNT - 1; j >= 1; j--) {
                        if (bases[j]) {
                            bases[j] = false;
                            totalScore++;
                        }
                    }
                    if (bases[0]) { // 1루 -> 3루
                        bases[2] = true;
                        bases[0] = false;
                    }
                    bases[1] = true;
                } else if (hitter == 3) { // 3루타
                    for (int j = BASE_COUNT - 1; j >= 0; j--) {
                        if (bases[j]) {
                            bases[j] = false;
                            totalScore++;
                        }
                    }
                    bases[2] = true;
                } else { // 홈런
                    for (int j = BASE_COUNT - 1; j >= 0; j--) {
                        if (bases[j]) {
                            bases[j] = false;
                            totalScore++;
                        }
                    }
                    totalScore++;
                }
                if (atBat == PLAYERS) atBat = 0;
            }
        }

        return totalScore;
    }
}