[백준] 17281 - ⚾ (JAVA)

1. 소요시간 : 1시간 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 구현, 브루트포스 알고리즘
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 문제 링크 : https://www.acmicpc.net/problem/17281
7. 푼 날짜 : 2023.05.13

1. 사용한 자료구조 & 알고리즘

백트래킹, 구현, 브루트포스 알고리즘

2. 사고과정

어떤 순서로 선수들을 배치할 것인가?
-> 처음에는 그리디 알고리즘으로 고민해봤다. 하지만 1번 이닝에서 선수들이 바뀌면 그 결과는 2번 이닝에도 영향을 미친다. 그래서 어떻게 고려하더라도 그리디 알고리즘은 성립될 수 없다고 생각. 백트래킹으로 풀어야 겠다고 생각했다.

선수들이 움직이는 것을 어떻게 구현할 것인가?
-> 이전까지 늘 그래왔듯이 움직이는 것은 queue로 구현했다. 움직이면 queue에서 poll하고, 몇칸 이동하는지 구하고 add하고.. 이런 식으로 1시간 10분쯤 전부 구현했다.
🧐 그리고 제출했는데 시간초과가 떴다. 이게 백트래킹 & 브루트포스 알고리즘 외에 다른 방법이 있나? 하고 내 알고리즘 설계가 틀렸다고 생각하고 다른 사람 풀이를 봤는데, 다른 사람도 크게 다르지 않았다.
👉 다만, 선수들이 움직이는 것을 queue가 아니라 boolean 형으로 선언하고 있었고, 이것이 시간초과가 난 원인이었다.

풀이를 보고 참고해서 움직이는 것을 boolean 형으로 선언해주니 정답.

3. 풀이과정

1. 백트래킹으로 모든 경우의 수의 조합을 구함.
2. 각각의 모둔 경우에 수에서, 1번 선수가 4번째 위치에 있는 경우에만 list에 담는다.
3. 아웃이 3번이 되면, 이닝을 1 증가시킨다. 아웃이 3 * N 이 되면, 모든 이닝을 수행한 것. break 한다.
4. 백트래킹으로 구한 각각의 경우의 수마다 max 값을 갱신.

4. 소스코드

import java.util.*;
import java.io.*;

public class Main {

	static boolean baseball[]=new boolean[3];
	static Integer arr[]=new Integer[9];
	static ArrayList<Integer[]> list=new ArrayList<>();
	static Queue<Integer> queue=new LinkedList<>();
	static boolean visited[]=new boolean[9];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st;

		backtracking(0);

		int N = Integer.parseInt(br.readLine());
		int person[][]=new int[N][9];

		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<person[0].length;j++) {
				person[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int max=0;
//
		for(int i=0;i<list.size();i++) {
			Integer now[]=list.get(i);
		
			int score=0;
			int out = 0;
			int idx = 0; //몇번쨰 이닝인지
			int end = 0; //몇번쨰 사람까지 갔는지
			Arrays.fill(baseball,false);
			while(out!=(N*3)) {
				int nowHit = person[idx][now[end++]];

				end%=9;

				if(nowHit==0) {
					out++;
					if(out%3==0) {
						idx++;
						Arrays.fill(baseball,false);
					}
				}
				else {
					if(nowHit==4) {
						score+=1;
						for(int j=0;j<baseball.length;j++) {
							if(baseball[j]) score++;
							baseball[j]=false;
						}
				
					}
					else {
						int addedScore = move(nowHit);
						score+=addedScore;
						baseball[nowHit-1]=true;
					}

				}

			

			}
			


			max=Math.max(max,score);


		}

		System.out.println(max);



	}
	public static int move(int nowHit) {

		
		int count = 0;
		
		for(int i=2;i>=0;i--) {
			if(baseball[i]) {
				if(i+nowHit>2) {
					count++;
				}
				else {
					baseball[i+nowHit] = true;
				}
				
				baseball[i]=false;
				
			}
			
		}

		return count;

	}

	public static void backtracking(int depth) {
		if(depth==9) {

			Integer copy[]=new Integer[arr.length];
			for(int i=0;i<copy.length;i++) {
				copy[i]=arr[i];
			}
			
			if(copy[3]==0)
				list.add(copy);

			return;
		}

		for(int i=0;i<arr.length;i++) {
			if(!visited[i]) {
				visited[i]=true;
				arr[depth]=i;
				backtracking(depth+1);
				visited[i]=false;
			}
		}


	}
}

5. 결과

첫 번쨰 제출은 큐를 사용해서 1번 틀렸다.
두 번째 제출은 boolean 배열을 썼으나 오타로 인해 1번 틀렸다.

6. 회고

queue는 O(1) 이니 그냥 신이야... 의 생각이 깨진 문제였다.
무조건 queue를 사용하면 안된다는 것을 확실하게 인지하게 되었다.

그리고 백트래킹으로 구할때 1번째 선수는 4번쨰 순서로 고정되어있는데, 그것을 고려하여 가지치기 하지 않고, 그냥 다 탐색한 후 1번째 선수가 4번째 순서인 경우에만 list에 담고 있는데, 이것도 불필요하게 시간이 더 많이 소모되는 요소이다. 개선이 필요해 보인다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212