[BOJ] 6897. 월드컵 - 백트래킹 c++
https://www.acmicpc.net/problem/6987
C++풀이
1. input[6][3] = 문제에서 주어진 결과 저장 배열 / games[6][3]= 임시 결과
2. 총 15경기에서 (A,B)경기 시 A가 이긴 경우, 비긴 경우, 진 경우 모두 완전 탐색으로 확인
3. round==15 시 input, games 배열 비교후 결과 출력
int result;
vector<pair <int, int>> team;
int games[6][3];
int input[6][5];
void dfs(int round){
if(round==15){
for(int j=0;j<6;j++){
for(int k=0;k<3;k++){
if(input[j][k]!=games[j][k]){
return;
}
}
}
result=1;
return;
}
int t1=team[round].first;
int t2=team[round].second;
games[t1][0]++;
games[t2][2]++;
dfs(round + 1);
games[t1][0]--;
games[t2][2]--;
//t1 t2가 비긴 경우
games[t1][1]++;
games[t2][1]++;
dfs(round + 1);
games[t1][1]--;
games[t2][1]--;
//t1가 패 t2가 패한 경우
games[t1][2]++;
games[t2][0]++;
dfs(round + 1);
games[t1][2]--;
games[t2][0]--;
}
int main() {
//total matches => 0 vs 1, 0 vs 2 ... 4 vs 5
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
team.push_back({i,j});
}
}
for(int i=0; i < 4; i++){
for(int j=0;j<6;j++){
for(int k=0;k<3;k++){
cin>>input[j][k];
games[j][k]=0;
}
}
dfs(0);
cout<<result<<" ";
result=0;
}
return 0;
}
Author And Source
이 문제에 관하여([BOJ] 6897. 월드컵 - 백트래킹 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mopevxw/BOJ-6897.-월드컵-백트래킹-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)