[BOJ/백준][Gold5] 6987 : 월드컵 (C++)

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

6987번: 월드컵

 

[난이도] Gold5
[유형] 백트래킹

[풀이]
총 6개의 0~5번 팀이 있다고 했을 때, 게임은 아래와 같이 총 15개가 나옵니다.
{{0,1},{0,2},{0,3},{0,4},{0,5},
 {1,2},{1,3},{1,4},{1,5},
 {2,3},{2,4},{2,5},
 {3,4},{3,5},
 {4,5}}

(p,q)가 게임하는 게임에 대해 p승,q패 / p패, q승 / p무, q무 총 3가지 경우가 나옵니다.
15개의 각 게임에 대해 백트래킹을 이용하여 3가지 경우를 모두 해보는 방식으로 문제를 해결할 수 있습니다.
3^15 = 14348907 이므로 시간내에 해결이 가능합니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int a[6][3];
pair<int,int> g[] = {{0,1},{0,2},{0,3},{0,4},{0,5},
                     {1,2},{1,3},{1,4},{1,5},
                     {2,3},{2,4},{2,5},
                     {3,4},{3,5},
                     {4,5}};
bool sol(int n){
    if(n==15){
        for(int i=0;i<6;i++)
            for(int j=0;j<3;j++) if(a[i][j]) return false;
        return true;  
    }
    auto [p,q] = g[n];
    if(a[p][1] && a[q][1]) {
        a[p][1]--,a[q][1]--;
        if(sol(n+1)) return true;
        a[p][1]++,a[q][1]++;
    }
    if(a[p][0] && a[q][2]) {
        a[p][0]--,a[q][2]--;
        if(sol(n+1)) return true;
        a[p][0]++,a[q][2]++;
    }
    if(a[p][2] && a[q][0]) {
        a[p][2]--,a[q][0]--;
        if(sol(n+1)) return true;
        a[p][2]++,a[q][0]++;
    }
    return false;
}
int main(){
    for(int i=0;i<4;i++){
        for(int j=0;j<6;j++)
            for(int k=0;k<3;k++) scanf("%d",&a[j][k]);
        printf("%d ",sol(0));
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/6987.cpp