[BOJ] 17281 야구

풀이가 매우매우 길어서 디코에도 안올라갔던 문제...
화면공유까지 켜서 물어보고 있는 나 레전드
dfs 과외 받고 있는 나 레전드
그걸 받아주고 있는 친구에게 무한 감사..

접근

1. 4번 타자를 고정하고 순열을 만든다.
2. 순서대로 이닝을 돌리는데, 마지막 선수를 저장해야하고, 삼진 아웃일 경우 다음 이닝으로 넘어가야한다.
3. 가장 큰 스코어를 비교 후 출력.

백트래킹을 dfs로 풀이할 때 depth가 배열 인덱스라고 생각하고 for문의 변수 값을 저장한다고 생각.. 아니 그림을 그리라고 그랬다.

그래서 깊이가 3(4번째 타자)일 경우 바로 dfs로 다시 들어가줬다.

풀이

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

public class Solution17281 {

    static int[] order;
    static int[][] players;
    static boolean[] base, visited;
    static int max, n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        order = new int[9];
        players = new int[n][9];
        base = new boolean[4];
        visited = new boolean[9];

        StringTokenizer st;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 9; j++) {
                players[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visited[0] = true;
        order[3] = 0;
        dfs(0);
        System.out.println(max);
    }

    static void dfs(int depth) {
        if(depth == 9) {
            playBaseball();
            return;
        }

        if(depth == 3) {
            dfs(depth+1);
            return;
        }

        for(int i = 0; i < 9; i++) {
            if(!visited[i]) {
                visited[i] = true;
                order[depth] = i;
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }

    static void playBaseball() {
        int startPlayer = 0;
        int score = 0;
        for(int i = 0; i < n; i++) {
            int outCnt = 0;
            base = new boolean[4];
            outer: while(true) {
                for(int j = startPlayer; j < 9; j++) {
                    int hitter = players[i][order[j]];
                    switch (hitter) {
                        case 0: outCnt++; break;
                        case 1:
                            for(int k = 3; k > 0; k--) {
                                if(base[k]) {
                                    if(k == 3) {
                                        score++;
                                        base[k] = false;
                                        continue;
                                    }
                                    base[k+1] = true;
                                    base[k] = false;
                                }
                            }
                            base[1] = true;
                            break;
                        case 2:
                            for(int k = 3; k > 0; k--) {
                                if(base[k]) {
                                    if(k == 3 || k == 2) {
                                        score++;
                                        base[k] = false;
                                        continue;
                                    }
                                    base[k+2] = true;
                                    base[k] = false;
                                }
                            }
                            base[2] = true;
                            break;
                        case 3:
                            for(int k = 3; k > 0; k--) {
                                if(base[k]) {
                                    score++;
                                    base[k] = false;
                                }
                            }
                            base[3] = true;
                            break;
                        case 4:
                            for(int k = 3; k > 0; k--) {
                                if(base[k]) {
                                    score++;
                                    base[k] = false;
                                }
                            }
                            score++;
                            break;
                    }
                    if(outCnt == 3) {
                        startPlayer = j+1;
                        if(startPlayer == 9) {
                            startPlayer = 0;
                        }
                        break outer;
                    }
                }
                startPlayer = 0;
            }
        }
        max = Math.max(max, score);
    }
}