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; } }