백준 6987 월드컵

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

6987번: 월드컵

완전 탐색을 통해 푸는 문제였습니다.

총 6개국으로 구성된 팀이 서로 한번씩은 경기를 해야합니다. 따라서 6*5/2 = 15 번의 경기를 가지게 됩니다.

O(3^15)시간 복잡도는 문제에서 제시한 시간제한을 만족합니다. 따라서 완전탐색을 통해 해결할 수 있습니다.

하지만 완전탐색이지만 좀 더 시간을 단축할 수 있는 여지가 있습니다. 저는 처음에 모든 경우의 수를 탐색한 후 

각 경우의 수를 문제에서 제시한 4가지 예제랑 비교하는 방식을 사용했습니다. 대략 600ms라는 많은 시간이 걸렸습니다.

맞으신 분들의 코드를 살펴봤을때 예제부터 시작해서 각 경기의 결과마다 승,무,패에 해당하는 부분을 빼주면서 만약 -1이 되는경우 이 후 탐색하지 않는 백트래킹 방식을 사용하여 시간을 단축하신 것을 확인했습니다. 이를 참고하여 다시 제출하여 풀어 시간을 단축할 수 있엇습니다.

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int arr[6][3];
int sum[3];
bool solve;
void dfs(int a,int b){
    if(a==5){
        solve=true;
        return;
    }
    for(int x=0;x<3;x++){
        arr[a][x]--;
        arr[b][2-x]--;
        if(arr[a][x]>=0 && arr[b][2-x]>=0){
            if(b==5){
                dfs(a+1,a+2);
            }
            else{
                dfs(a,b+1);
            }
        }
        arr[a][x]++;
        arr[b][2-x]++;
    }
}
int main(){
    for(int test=0;test<4;test++){
        for(int x=0;x<3;x++) sum[x]=0;
        solve=false;
        for(int x=0;x<6;x++){
            for(int y=0;y<3;y++){
                cin>>arr[x][y];
                sum[y]+=arr[x][y];
            }
        }
        dfs(0,1);
        if(sum[0]!=sum[2] || 30-sum[1] != sum[0]+sum[2]) solve=false;
        cout<<solve<<" ";
    }
}