[백준 17281] 야구 자바 - 완전탐색

문제

17281번: ⚾

 

접근방식

야구를 잘 몰라서 많이 헤맸던.. 순열 구할 때 DFS로 1번 선수가 4번 타자가 되는 경우를 고정해서 구했고 그 후에 점수 구하는 방법은 문제에서 설명한 내용들을 기준으로 구현해 줬다. 처음에 베이스 밟는 걸 큐로 만들어서 관리하려고 했는데 시간초과 나서 배열로 바꿨다. 3루 쪽으로 당겨주는 로직을 잘 짜둬서 1,2,3번 나누지 않고 한 번에 해결이 가능했다.

public static int Game() {
		int idx = 0;
		int score = 0; 
		int out;
		int[] base = new int[3]; //base 3개 

		for (int i = 0; i < N; i++) {	//이닝수만큼 반복 
			//초기
			out = 0;
			init(base); 
			while(true) {
				int now = members[i][pm[idx%9+1]];
				if(now == 0) { //아웃 
					out++;
					if(out == 3) { //삼진 아웃 
						idx++; //이닝 마지막 타자의 다음 타자 
						break;
					}
				}//홈런이면 모든 주자들 수만큼 점수 추가 
				else if(now==4){	
					for (int x : base) {
						if(x == 1) score++;
					}
					score++; //타자 1점 추가 
					init(base); //초기화 
				}else {
					//점수 계산 
					for(int j = 2; j > 2-now; j--) {
						score += base[j];
					}
					//3루부터 당겨주고 
					for (int j = 2; j >= 0; j--) {
						if(j == now-1) base[j] = 1;
						else if(j < now-1) base[j] = 0;
						else base[j] = base[j-now];
					}
				}
				idx++;
			}
		}
		return score;
	}

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, pm[],members[][],max;
	public static boolean[] visited;
	
	public static void DFS(int count) {
		if(count == 10) { 
			int score = Game(); //게임 시작 
			max = Math.max(max, score);
			return;
		}
		else {
			//4번 타자는 1번 선수로 고정 
			if(count == 4) {
				pm[count] = 1;
				DFS(count+1);
			}
			else {
				//1번은 제외 
				for (int i = 2; i <= 9; i++) {
					if(!visited[i]) {
						visited[i] = true;
						pm[count] = i;
						DFS(count+1);
						visited[i] = false;
					}
				}
			}
		}
	}
	
	public static int Game() {
		int idx = 0;
		int score = 0; 
		int out;
		int[] base = new int[3]; //base 3개 

		for (int i = 0; i < N; i++) {	//이닝수만큼 반복 
			//초기
			out = 0;
			init(base); 
			while(true) {
				int now = members[i][pm[idx%9+1]];
				if(now == 0) { //아웃 
					out++;
					if(out == 3) { //삼진 아웃 
						idx++; //이닝 마지막 타자의 다음 타자 
						break;
					}
				}//홈런이면 모든 주자들 수만큼 점수 추가 
				else if(now==4){	
					for (int x : base) {
						if(x == 1) score++;
					}
					score++; //타자 1점 추가 
					init(base); //초기화 
				}else {
					//점수 계산 
					for(int j = 2; j > 2-now; j--) {
						score += base[j];
					}
					//3루부터 당겨주고 
					for (int j = 2; j >= 0; j--) {
						if(j == now-1) base[j] = 1;
						else if(j < now-1) base[j] = 0;
						else base[j] = base[j-now];
					}
				}
				idx++;
			}
		}
		return score;
	}
	
	//초기화 함수 
	public static void init(int[] base) {
		Arrays.fill(base, 0);
	}
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());	
        
        members = new int[N][10];
        pm = new int[10];
        visited = new boolean[10];
        
        for (int i = 0; i < N; i++) {
        	st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= 9; j++) {
				members[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        
        //순열  
        DFS(1);
        
        System.out.println(max);
        
    }
}