문제

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

풀이

조건

• 총 N이닝 동안 게임을 진행해야 한다.
• 한 이닝에 3아웃이 발생하면 이닝이 종료된다.
• 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다.
• 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다.
• 타순은 이닝이 변경되어도 순서를 유지해야 한다.
  • 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다.
• 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다.
• 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다.
• 이닝이 시작될 때는 주자는 없다.
• 1번 선수는 4번 타자로 미리 결정되어있다.
• 타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다.
  • 0 -> 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다.
  • 1 -> 안타: 타자와 모든 주자가 한 루씩 진루한다.
  • 2 -> 2루타: 타자와 모든 주자가 두 루씩 진루한다.
  • 3 -> 3루타: 타자와 모든 주자가 세 루씩 진루한다.
  • 4 -> 홈런: 타자와 모든 주자가 홈까지 진루한다.

풀이 순서

• 미리 4번 자리에 1번 선수를 넣어둔다.
• 백트래킹을 사용해 선수들의 순서를 조합한다.
• 백트래킹 종료 시에 조합된 순서대로 게임을 시작한다.
  -base[] 배열을 사용해 베이스에 나가 있는 선수들을 구현한다.
  • base[1] : 1번 베이스
  • base[2] : 2번 베이스
  • base[3] : 3번 베이스
• 3 아웃이 되기 전 까지 한 이닝 동안 선수들의 게임을 반복한다.
• 이닝이 끝나면 총 게임 점수에 해당 이닝에서 얻은 점수를 더한다.
• 주석을 통해 이해하는 것이 쉽다.

코드

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

public class Main {
    
	static int inning; // 이닝 수
	static int[][] playerStat; // 입력받는 선수의 이닝 별 능력
	
	static boolean[] isPlayerChecked; // 조합에서 사용 할 체크 배열
	static int[] lineUp; // 선수 순서 조합한 배열
	
	static Queue<Integer> que; // 야구에서 베이스를 의미할 큐
	static int out; // 아웃 횟수
	
	static int max = -1;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	
    	inning = Integer.parseInt(br.readLine());
    	
    	playerStat = new int[inning][10];
    	for(int i=0; i<inning; i++) {
    		st = new StringTokenizer(br.readLine(), " ");
    		for(int j=1; j<=9; j++) {
    			playerStat[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	// 선수 순서 정함
    	isPlayerChecked = new boolean[10];
    	lineUp = new int[10];
    	
    	lineUp[4] = 1; // 4번 타자로 1번 선수를 미리 넣어 둠
    	isPlayerChecked[4] = true; // 4번 자리는 미리 넣었으므로 체크 처리
    	
    	playerSeq(2); // 1번 선수의 자리는 이미 있으므로 2번 선수부터 시작한다.
    	
    	System.out.println(max); // 최대 점수 출력
    	
    }
    
    // 선수 순서 정함
    static void playerSeq(int num) {
    	// 9명 다 채웠으면 종료
    	if(num == 10) {
    		
    		// 야구 게임 플레이
    		int score = play();
    		
    		max = Math.max(max, score);
    		
    		return;
    	}
    	
    	// 현재 선수를 1번 자리부터 9번 자리까지 넣어보며 재귀 호출
    	for(int i=1; i<=9; i++) {
    		
    		if(!isPlayerChecked[i]) {
    			isPlayerChecked[i] = true;
    			
    			lineUp[i] = num;
    			playerSeq(num + 1);
    			
    			isPlayerChecked[i] = false;
    		}
    	}
    }
    
    static int play() {
    	int sum = 0;
    	
    	int idx = 1; // 1번 타자부터 시작
    	for(int r=0; r<inning; r++) {
    		int inningScore = 0; // 현재 이닝에서 얻는 점수
    		out = 0; // 현재 이닝에서 아웃의 수
    		boolean[] base = new boolean[4]; // true : 해당 베이스에 선수가 있음, false : 해당 베이스에 선수가 없음
    		
    		// 3 아웃이 되기 전까지 반복
    		while(out < 3) {
    			switch(playerStat[r][lineUp[idx]]) {
    				// 아웃
		    		case 0:
		    			out++;
		    			break;
		    		// 1루타
		    		case 1:
		    			if(base[3]) {
		    				inningScore++;
		    				base[3] = false;
		    			}
		    			if(base[2]) {
		    				base[3] = true;
		    				base[2] = false;
		    			}
		    			if(base[1]) {
		    				base[2] = true;
		    			}
		    			base[1] = true;
		    			break;
		    		// 2루타
		    		case 2:
		    			if(base[3]) {
		    				inningScore++;
		    				base[3] = false;
		    			}
		    			if(base[2]) {
		    				inningScore++;
		    			}
		    			if(base[1]) {
		    				base[3] = true;
		    				base[1] = false;
		    			}
		    			base[2] = true;
		    			break;
		    		// 3루타	
		    		case 3:
		    			if(base[3]) {
		    				inningScore++;
		    			}
		    			if(base[2]) {
		    				inningScore++;
		    				base[2] = false;
		    			}
		    			if(base[1]) {
		    				inningScore++;
		    				base[1] = false;
		    			}
		    			base[3] = true;
		    			break;
		    		// 홈런	
		    		case 4:
		    			if(base[3]) {
		    				inningScore++;
		    				base[3] = false;
		    			}
		    			if(base[2]) {
		    				inningScore++;
		    				base[2] = false;
		    			}
		    			if(base[1]) {
		    				inningScore++;
		    				base[1] = false;
		    			}
		    			inningScore++;
		    			break;
    			}
    			
    			// 다음 타자로
    			idx++;
    			// 만약 10번 타자가 되면 다시 1번 타자로 되돌림
    			if(idx >= 10) {
    				idx = 1;
    			}
    		}
    		
    		// 해당 이닝에서 얻은 점수를 총 게임 점수에 더해줌
    		sum += inningScore;
    		
    	}
    	
    	// 이번 게임에서 얻은 점수를 반환함
    	return sum;
    }

}

정리

• 처음에 선수들이 베이스에 있는 것을 Queue를 통해 구현했었는데 시간도 오래 걸리고 맞는 케이스도 있고 안 맞는 케이스도 있었다.