https://www.acmicpc.net/problem/17281
17281번: ⚾
⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종
www.acmicpc.net
코드설명
DFS(깊이우선탐색) + 일반 순열(Normal Permutation) + 구현 문제입니다.
문제 중에서 가장 중요한 부분은,
야구타자의 순서 1번부터 9번 타순을 순열로 만들어내고, 4번 타순을 고정시키는 방법에 대하여입니다.
야구타순에서 1번 타순에는 2 가 들어갈 수 있습니다.
2번 타순에는 3, 3번타순에는 4, 4번타순에는 "1"이 고정적으로 들어갑니다. 5번 타순에는 5가 들어갑니다.
이 과정에서 보면 결국은 모든 순서를 완전탐색하여야한다는것을 알 수 있습니다.
타순같은경우 조합이 아닌 순열을 사용하는데 중복순열이 아닌 일반 순열(Normal Permutation)을 사용합니다. 각 타자는 1명씩 존재하고, 앞의 타자가 1루수에 나가느냐, 2루수에 나가느냐에 따라 점수가 달라지기에 순열을 사용해야합니다.
이 과정에서 1번 타자를 4번 타순에 고정시키기 위해 순열을 생성하면서 해당 4번 level에는 다른 재귀로 분할되도록 처리합니다.
여기서 visited는 각 타자의 사용여부를 나타냅니다.
order[level] = i 같은경우는 level번쨰 타순. 예시로들면 첫번째 타순에 i번쨰 선수를 두어라 라는 의미입니다.
i번쨰 선수는 문제에서 주어지듯 1번 타자는 반드시 4번 타자부터 진행되므로 1번은 넘어가고 2번부터 진행합니다.
문제로직입니다.
- 순열 함수 getNormalPermutationForSelectHitter 함수는 타자 순서의 순열을 생성합니다.
- level이 10이면, 즉 타자 순서가 결정되었으면 baseballStart 함수를 호출하여 야구 게임을 진행하고 점수를 갱신합니다.
- level이 4이면 4번째 타자의 위치가 이미 정해졌으므로 다음 레벨로 넘어갑니다.
- 그 외의 경우, 가능한 모든 타자 순서에 대해 재귀적으로 호출하여 순열을 완성합니다.
- 야구 게임 시작 함수 baseballStart 함수는 타자 순서대로 야구 게임을 시작합니다.
- 각 이닝마다 아웃이 3번 발생할 때까지 진행하며, 각 타자의 타격 결과에 따라 점수를 계산합니다.
- 이닝이 끝나면 다음 이닝으로 넘어가고, 게임이 종료될 때까지 반복합니다.
또한 만약 한 이닝에서 아웃이 안된다면, 해당 이닝을 계속해서 돕니다.
처음에는 만약 한 이닝의 Cycle을 모두 돈다면, 다음 이닝으로 넘아가도록 하여 틀렸습니다.
추가적인 것들은 코드에 주석으로 남겨두었습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N,M, K;
public static int answer = 0;
public static int[][] hitScore;
public static int[] hitter;
public static boolean[] visited;
public static int[] juja = new int[4];
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());
hitScore = new int[N][10];
hitter = 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++) {
hitScore[i][j] = Integer.parseInt(st.nextToken());
}
}
visited[1] = true;
hitter[4] = 1;
simulate(1);
System.out.println(answer);
}
public static void simulate(int level) {
if(level > 9) {
// System.out.println("=========================");
// for(int i=1;i<10;i++) {
// System.out.print(" "+hitter[i]);
// }
// System.out.println();
calculate();
return ;
}
if(level == 4) {
simulate(level + 1);
return ;
}
for(int i=2;i<=9;i++) {
//해당 타자를 이미 배치했는지 확인합니다.
if(visited[i] == false) {
visited[i] = true;
hitter[level] = i;
simulate(level + 1);
// hitter[level] = 0;
visited[i] = false;
}
}
}
public static void calculate() {
int inning = 0;
int outCnt = 0;
int score = 0;
int[] juja = new int[4];
while(inning < N) {
for(int j=1;j<=9;j++) {
int hitResult = hitScore[inning][ hitter[j] ]; //i번쨰 이닝에 1타순의 상대의 결과는?
if(hitResult == 1) {
score += juja[3];
juja[3] = 0;
juja[3] = juja[2];
juja[2] = juja[1];
juja[1] = 1;
}else if(hitResult == 2) {
score += juja[3] + juja[2];
juja[3] = 0;
juja[2] = 0;
juja[3] = juja[1];
juja[2] = 1;
juja[1] = 0;
}else if(hitResult == 3) {
score += juja[3] + juja[2] + juja[1];
juja[3] = 0;
juja[2] = 0;
juja[1] = 0;
juja[3] = 1;
}else if(hitResult == 4) {
score += juja[3] + juja[2] + juja[1] + 1;
juja[3] = juja[2] = juja[1] = 0;
}else if(hitResult == 0) {
outCnt += 1;
}
if(outCnt == 3) {
outCnt = 0;
inning += 1;
juja = new int[4];
// break; 이닝이 넘어가도 현재 Index에서 계속 타자가 진행되므로 자연스럽게 진행되도록 합니다.
}
if(inning == N) { //만약 inning이 끝난다면 해당 바로 종료시킵니다.
answer = Math.max(answer, score);
return;
}
}
}
answer = Math.max(answer, score);
return;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int[][] arr;
public static boolean[] visited = new boolean[10];
public static int[] order = new int[10]; //i번째 타석에 몇번째 타자가 들어갈 것인가?
public static int answer = 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());
arr = new int[N+1][10];
for(int i=1;i<=N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=1;j<=9;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
order[4] = 1;
getNormalPermutationForSelectHitter(1); //1번 타자부터 10번타자까지의 일반순열을 구합니다.
System.out.println(answer);
}
//1 2 3 4 5 6 7 8 9 -> 이것을 순열로 표현할 것 입니다. 4번 타석은 1번으로 고정시켜야합니다. 가장 첫 값은 2 3 4 1 5 6 7 8 9 이 될 것 입니다.
public static void getNormalPermutationForSelectHitter(int level) {
if( level == 10) {
// 이제 야구 경기를 시작할 것 입니다.
answer = Math.max(answer, baseballStart());
return ;
}
if(level == 4) { //4번째 타석은 이미 정해졌으니 넘어갑니다.
getNormalPermutationForSelectHitter(level + 1);
return ;
}
for(int i=2;i<10;i++) {
if(visited[i] == false) {
visited[i] = true;
order[level] = i;
getNormalPermutationForSelectHitter(level + 1);
// order[i] = -1; //-1 쓰면 순열에서 올바르게 바뀌지않습니다.
visited[i] = false;
}
}
}
public static int baseballStart() {
//1. 야구를 타석 순서대로 게임을 시작합니다. (1 ~ 9)
int cnt = 1;
int[] base = new int[4];
int score = 0;
int startHitter = 1;
//현재 이닝
while( cnt <= N) {
base = new int[4];
//아웃카운트는 3입니다.
int outCnt = 3;
//각 이닝이 시작됩니다. 3 2 1 outCount일때만 작동합니다.
while(outCnt > 0) {
for(int i=startHitter; i<=9; i++) {
// System.out.println("outCnt:"+outCnt+" cnt:"+cnt+" orderID:"+order[i]+"arr[cnt][order[i]:"+arr[cnt][order[i]]);
int hitScore = arr[cnt][order[i]]; //타자가 친 크기.
//만약 아웃이라면,
if(hitScore == 0) {
outCnt -= 1;
}
//만약 안타라면
else if(hitScore == 1) {
score += base[3]; //3루수가 나갑니다.
base[3] = base[2];
base[2] = base[1];
base[1] = 1;
}
//만약 2루타라면,
else if(hitScore == 2) {
score += base[3] + base[2];
base[3] = base[1];
base[2] = 1;
base[1] = 0;
}
//만약 3루타라면,
else if(hitScore == 3) {
score += base[3] + base[2] + base[1];
base[3] = 1;
base[2] = base[1] = 0;
}
//만약 홈런이라면,
else if(hitScore == 4) {
score += base[3] + base[2] + base[1] + 1;
base[3] = base[2] = base[1] = 0;
}
if(outCnt == 0) { //만약 outCnt 삼진아웃이라면 나갑니다. 그리고 startHitter는 다음 이닝에 연속해서 사용하기 위해 값 갱신합니다.
startHitter = ( i + 1) <= 9 ? i+1 : 1;
break;
}
if(i == 9) startHitter = 1;
}
}
cnt+=1; //이닝 증가.
}
return score;
}
}