[ 백준 17281번 ] Gold IV - ⚾ ( 야구) - 자바

문제 설명 

 

문제

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다.

두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.

공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다.

타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다.

• 안타: 타자와 모든 주자가 한 루씩 진루한다.
• 2루타: 타자와 모든 주자가 두 루씩 진루한다.
• 3루타: 타자와 모든 주자가 세 루씩 진루한다.
• 홈런: 타자와 모든 주자가 홈까지 진루한다.
• 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.

한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자.

입력

첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다.

• 안타: 1
• 2루타: 2
• 3루타: 3
• 홈런: 4
• 아웃: 0

각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.

출력

아인타팀이 얻을 수 있는 최대 점수를 출력한다.

 

문제가 길어서 처음에는 이해하기가 힘들었다. 야구를 몰라서인가, 이닝이라는 것도 처음 들었다. 

우선 문제를 읽어보면 차근히 해결할 수 있는 "브루트포스(완전탐색)" 알고리즘이다. 

먼저 문를 시작하기 위해 

두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다.

를 통해 DFS를 통해 가능한 순서를 담은 순열을 생성한다. order[] = new int[9]; // 순서를 담을 배열 

여기에서 order[3] = 0으로 고정된다.

순서 순열은 dfs => check(현재 순서, visitied(방문확인), order, player) 로 만들게 된다. 

순서 순열을 만드는 함수 

dfs를 돌며 하나씩 order를 생성해 총 40320 경우의 수가 생성된다. 

하나의 순열 s==9로 order[]의 값이 0~8까지 모두 채워졌다면, 

순서에 따라 이닝 결과를 나타내는 함수 

이후 고정된 플레이어 순서에 따라 경기가 시작된다. 

먼저 저장될 값을 cnt로 선언한다. 총 N이닝 동안 진행하기 떄문에, for문으로 전체 이닝을 돌게 된다.

여기에서 order로 고정된 타순이 나타나고, 3아웃이 발생할 때 반복문은 종료되기 떄문에, while(out<3)으로 out의 개수가 3을 넘지 않으면 계속 반복문을 돌게 된다.

타석에 서는 번호는 t에 저장된다. 0~8로 돌다 9가 되면다시 0이 되어 1번 타자가 다시 타석에 선다. 

타자가 공을 쳐서 얻을 수 있는 결과에 따라 값이 달라지는데, 

1루수에 선수가 있으면 1 , 아니면 0이 된다. 

타자가 공을 친 결과에 따른 득점 

• 안타: 타자와 모든 주자가 한 루씩 진루한다.
• 2루타: 타자와 모든 주자가 두 루씩 진루한다.
• 3루타: 타자와 모든 주자가 세 루씩 진루한다.
• 홈런: 타자와 모든 주자가 홈까지 진루한다.
• 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다

위 이 규칙을 따라, 코드가 짜여진다. 

위 반복문을 돌며 이닝을 끝까지 돌면, cnt의 값이 결과값이 된다. 

전체 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 야구 {
	static int ans;
	static int N; 
	static int count = 0; 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st; 
		N = Integer.parseInt(br.readLine());
		int[][] player =new int[N][9];
		for(int n = 0; n<N;n++) {
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < 9; i++) {
				player[n][i]= Integer.parseInt(st.nextToken());
			}
		}
		// 플레이어의 순서를 정하는 순열 
		int [] order = new int[9];
		order[3] = 0;
		// order 만들어올 순열 
		boolean[] visitied =new boolean[9];
		visitied[0] =true;
		check(0,visitied, order, player);
		System.out.println(ans);
	}

	private static void check(int s,boolean[] visitied, int[] order, int[][] player) {
		if(s==9) {
			// 이닝별 
			int cnt = 0 ;
			int t =-1 ; //이게 타자 순서..
			for(int n = 0; n<N;n++) { // 이닝
				int out = 0; 
				int l1=0,l2=0,l3=0;
				while(out<3) {
					t++;
					if(t==9)t=0;
					switch(player[n][order[t]]) {
					case 0:
						out++;
						break;
					case 4:
						cnt+=l1+l2+l3+1;
						l1=0;l2=0;l3=0;
						break;
					case 3:
						cnt+=l3+l2+l1;
						l3=1;l2=0;l1=0;
						break;
					case 2: 
						cnt+=l3+l2;
						l3=l1;l2=1;l1=0;
						break;
					case 1: 
						cnt+=l3;
						l3=l2;l2=l1;l1=1;
						break;
					}
				}
			}
			ans= cnt>ans?cnt:ans;
			return;
		}
		for(int i = 1; i<9;i++) {
			if(!visitied[i]) {
				order[s] = i;
				visitied[i] = true;
				if(s==2)check(4, visitied, order, player);
				else check(s+1, visitied, order, player);
				visitied[i] = false;
			}
		}
	}
}