[백준] 17282 - 야구

 순열의 경우의 수(타자 순서)에 따른 결과값(야구 점수)를 일일히 대조해서 각각의 순열 중 최고점을 찾는 문제. 

순열을 구하면서 재귀가 사용되었고, 순열에 따른 결과값을 모두 다 살펴본다는 면에서 완전탐색 문제이다.

 

 문제 자체는 어렵지 않은데 (특히 야구를 자주 봤다면,,,,ㅎ) 일반적인 조건이 아닌 특별한 조건(특정 인덱스(4번타자)가 고정되어 있음(0번) -> 따로 처리로직을 짜야 함)이 붙었으며, 타자가 안타, 홈런, 아웃을 했을 떄의 경우의 수를 각각 따로 처리해줘야 해서 좀..골치가 아프다. 특히 인풋으로 상상 이상의 값이 들어오는 걸 감안한다면,, 점수를 계산할 때 모든 경우의 수를 다 체크했는지 확인해줘야 한다. 

 

 아웃일 땐 간단한데, 홈런을 쳤을 때 1,2,3루를 모두 리셋해야 하며, 점수를 베이스에 있는 주자들 + 홈런을 친 타자 까지 고려해 주어서 더해야 한다. 안타를 쳤을 경우 베이스의 주자들이 홈인하는 경우, 이동하는 경우를 for문으로 처리해주고 (떠난 자리는 떠났다고 표시 해주는 것도 잊지 말기) 안타를 친 주자가 친 안타 수만큼 무조건 안착해야 한다.

 

 또한 이닝별로 공유되는 값(순서 - 마지막 타자 이후에 0으로 돌아옴 & 이닝이 바뀌어도 순서 유지, 게임 점수) 과 이닝이 바뀔때마다 초기화 해줘야되는값(베이스 상태, 아웃카운트 리셋)을 꼼꼼히 고려해줘야한다.

 

 한 열시반-열한시 정도에 시작해서 한시가 조금 안되서 끝났으니 두시간 반-세시간 정도 걸린 듯? (참고로 아직 브론즈도 못벗어난 알고알못..알린이 신세임니다ㅜ)

 

+) 순열의 경우의 수가 8!(9명의 선수 중 한 선수 고정) 이기 때문에 만약 이클립스에서 순열을 일일이 확인해 보려고 한다면  콘솔의 출력 한계를 늘려줘야 모든 경우의 수를 다 볼 수 있다. 이클립스 IDE 기준 Windows > Preferences > Run/Debug > Console 에서  Console buffer size를 100배정도? 늘려줘야 한다..

 

처음에 이거 몰라서 순열 다 못구한줄 앎ㅎ

 

소스 코드 (Java 8)

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

public class Main {
	static int totalInning;
	static int[] playerTurn = new int[9];
	static int[][] playerScore;
	static boolean[] used = new boolean[9];
	static int maxScore;
	static int curScore;
	static boolean[] board = new boolean[3];
	
	public static void updateBoard(int result) {
		
		for(int i=2; i>=0; i--) { //역순회
			//홈인
			if(board[i] && i+result >=3 ) {
				board[i] = false;
				curScore++;
			}
			//베이스 이동
			else if(board[i]) {
				board[i+result] = true;
				board[i] = false;
			}
		}
		//뉴비 안착
		board[result-1] = true;
	}
	
	public static void clearBoard() {
		for(int i=0; i<3; i++)
			board[i] = false;
	}
	
	public static int countRunners() {
		int sum = 0;
		for(int i=0; i<3; i++) {
			if(board[i])
				sum+=1;
		}
		return sum;
	}
	
	//maxScore 비교해서 리셋.
	public static void playGame() {
		int curInning = 0; //현 이닝
		curScore = 0; //점수 > 이닝마다 공유
		int turn = 0; //순서 > 이닝마다 공유
		int outCnt;
		int result;
		
		//게임 새로 시작.
		while(curInning != totalInning) {
			//보드, 아웃카운트 > 이닝 내에서 변화.
			outCnt = 0;
			clearBoard();
			//이닝 새로 시작. turn과 score 유지.
			while(outCnt != 3) {
				result = playerScore[curInning][playerTurn[turn]];
				switch(result) {
				case 0: //아웃
					outCnt++;
					break;
				case 4: 
					// 홈런: 타자 + 주자 포함하기!
					curScore += countRunners();
					curScore += 1;
					clearBoard();
					break;
				default: //그 외 안타
					updateBoard(result);
				}
				turn = (turn+1)%9; //순서 돌아감.
			}
			curInning++;
		}
		
		//최대 점수 업데이트.
		if(curScore > maxScore)
			maxScore = curScore;
		
	}
	
	//nPr n = 9, r = 9, 3번 인덱스 0으로 고정.
	public static void perm(int idx) {
		if(idx == 9) { //순열 완성 했으니 게임 진행
			playGame();
			return;
		}
		if( idx == 3 ) {
			perm(idx+1);
		}
		else {
			for(int i=1; i<9; i++) {
				if(!used[i]) {
					used[i] = true;
					playerTurn[idx] = i;
					perm(idx+1);
					used[i] = false;
				}
			}
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		playerTurn[3] = 0; used[0] = true; // 최애 4번타자 고정.
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		totalInning = Integer.parseInt(br.readLine());
		playerScore = new int[totalInning][9];
		
		for(int i=0; i<totalInning; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<9; j++) {
				playerScore[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		perm(0);
		System.out.println(maxScore);
	}
}

 

변수 설명

• playerScore: 각 이닝 별 선수들의 결과 값을 int형 2차원 배열로 저장
• playerTurn: 몇번째에 몇번 선수가 오는지. 여기서 몇 '번째' 는 야구에서의 타순을 의미하며 몇'번'선수는 그 선수의 이름을 숫자로 나타냈다고 보면 된다. 만약 playerTurn[0] = 3; 이면 0번 타순, 즉 맨 첫 타순에 3번 선수가 들어서게 되는 것이다.
• board: 각 베이스의 상태를 boolean형 1차원 배열로 저장. 주자가 있다면 true, 주자가 없다면 false로 설정함
• turn: 현재 몇번 타순인지를 저장함. 0~8번 까지 있으므로 다음 타자는 (turn+1)%9로 계산하여 8번 타자 이후엔 0번 타자로 다시 돌아올 수 있도록 한다.

메소드 설명

• perm(int idx): 9명의 선수를 줄세워 타순을 정하는 순열. 매개변수인 idx는 현재 정해야 하는 타순이 몇번째인지를 의미하며, 3번 타순은 0번 선수로 이미 정해져 있는 것을 고려하여 이 때는 따로 선수를 뽑지 않는다.
• playGame(): 해당 타순에 따른 게임 하나.
• countRunners(): 현재 주자들이 몇 명인지 리턴
• updateBoard(): 안타에 따른 베이스 이동, 홈인 등등 을 업데이트
• clearBoard(): 1루, 2루, 3루를 모두 다 비우기. 홈런이거나, 이닝이 변화 했을 때 사용.