코딩테스트/그래프|트리
[DFS 순열] 백준 17281 ⚾(야구) C++
유(YOO)
2022. 2. 3. 13:19
https://www.acmicpc.net/problem/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;
}