[DFS 순열] 백준 17281 ⚾(야구) C++

 

https://www.acmicpc.net/problem/17281

17281번: ⚾

#include <bits/stdc++.h>

using namespace std;

int n, ans, result[52][10], order[10];
bool visited[10];

int game() { // stl 큐 사용하면 시간 초과(큐 직접 구현)
	int idx = 1, out = 0, score = 0;
	for (int i = 1; i <= n; i++) {
		out = 0; // 이닝마다 아웃 횟수 초기화
		int front = 0; // 홈 위치(홈->3루->2루->1루)
		int ground[3]; // 큐
		memset(ground, 0, sizeof(ground)); // 3루, 2루, 1루 선수 번호 이닝마다 초기화
		while (out < 3) {
			if (idx % 10 == 0) idx = 1;
			if (result[i][order[idx]] == 0) out++;
			else {
				for (int j = 0; j < result[i][order[idx]]; j++) {
					if (ground[front] != 0) score++; // 3루 선수 들어옴
					if (j == 0) ground[front] = order[idx]; // 해당 선수 1루로
					else ground[front] = 0;
					front++;
					front %= 3;
				}
			}
			idx++;
		}
	}
	return score;
}

void dfs(int depth) { // 중복 없는 순열(순서 고정)
	if (depth == 10) {
		int val = game();
		ans = max(ans, val);
		return;
	}

	for (int i = 2; i < 10; i++) {
		if (depth == 4) {
			dfs(depth + 1);
			break;
		}
		if (visited[i]) continue;
		visited[i] = true;
		order[depth] = i;
		dfs(depth + 1);
		visited[i] = false;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> result[i][j];
		}
	}

	// 미리 4번 타자 지정
	order[4] = 1;
	visited[1] = true;
	dfs(1);

	cout << ans;
}