[백준,c++] 6987번 - 월드컵

문제

6987번: 월드컵

 

코드

#include <iostream>
#include <memory.h>

using namespace std;

int arr[6][3];

bool flag_check(){
    for(int i=0; i<6; i++){
        for(int k=0; k<3; k++){
            if(arr[i][k] != 0) return false;
        }
    }
    return true;
}

bool flag = false;

void backtracking(int idx, int next, int depth){
    if(idx == 5 && depth == 15){
        if(flag_check()) flag = true;
        return;
    }
    if(arr[idx][0] > 0 && arr[next][2] > 0){
        arr[idx][0]--;
        arr[next][2]--;
        backtracking(idx, next + 1, depth + 1);
        arr[idx][0]++;
        arr[next][2]++;
    }
    if(arr[idx][1] > 0 && arr[next][1] > 0){
        arr[idx][1]--;
        arr[next][1]--;
        backtracking(idx, next + 1, depth + 1);
        arr[idx][1]++;
        arr[next][1]++;
    }
    if(arr[idx][2] > 0 && arr[next][0] > 0){
        arr[idx][2]--;
        arr[next][0]--;
        backtracking(idx, next + 1, depth + 1);
        arr[idx][2]++;
        arr[next][0]++;
    }
    if(idx < 5) backtracking(idx + 1, idx + 2, depth);
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i=0; i<4; i++){
        memset(arr, 0, sizeof(arr));
        int c = 0;
        for(int k=0; k<18; k++){
            cin>>arr[k/3][c];
            c++;
            if(c == 3) c = 0;
        }
        backtracking(0, 1, 0);
        if(flag) cout<<1<<' ';
        else cout<<0<<' ';
        flag = false;
    }
    
}

 

풀이

처음에 백트랙킹 없이 단순하게 조건문 몇 개 추가해서 승 무 패의 합을 가지고 판단할 수 있을까 생각했지만 결국 그런 식으로 구현하지 못한다는 사실을 깨달았습니다.

일단 각 나라들은 모든 나라와 무조건 한번씩 경기를 진행해야 합니다. 문제 풀이 아이디어는 아래의 연산자 끼워넣기와 거의 유사하게 풀었습니다.

[백준,c++] 15658번 - 연산자 끼워넣기 (2)

경기 진행은 잘 보면 다음과 같습니다.

• A 나라는 B, C, D, E, F의 나라와 경기를 진행해야 합니다.
• B 나라는 C, D, E, F 나라와 경기를 진행해야 합니다. (A가 없는 이유는 위에서 A 나라를 기준으로 잡았을 때 A와 B나라는 경기를 진행했기 때문입니다.)
• C나라는 D, E, F 나라와 경기를 진행해야 합니다.
• D나라는 E, F 나라와 경기를 진해해야 합니다.
• E나라는 F 나라와 경기를 진행해야 합니다.

즉, 총 15번의 경기를 진행하게 됩니다. 

문제 풀이 아이디어는 다음과 같습니다.

A나라가 B, C, D, E, F 각각의 나라와의 경기에서 이겼을 때, 비겼을 때, 졌을 때의 경우의 수를 탐색하면서 최종적으로 모든 나라의 승 무 패 가 0이 되는지 확인하면 됩니다.