[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;
    
    
}

좋은 웹페이지 즐겨찾기