월드컵(DFS)

문제 설명

---

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다.

네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오. 단, 부분 점수는 없다.

입력 설명

---

첫째 줄부터 넷째 줄까지 각 줄마다 6개국의 결과가 나라별로 승, 무승부, 패의 순서로 빈칸을 하나 사이에 두고 18개의 숫자로 주어진다.

출력 설명

---

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 1, 불가능한 결과는 0을 빈칸을 하나 사이에 두고 출력한다.

입력 예시

---

5 0 0 3 0 2 2 0 3 0 0 5 4 0 1 1 0 4
4 1 0 3 0 2 4 1 0 1 1 3 0 0 5 1 1 3
5 0 0 4 0 1 2 2 1 2 0 3 1 0 4 0 0 5
5 0 0 3 1 1 2 1 2 2 0 3 0 0 5 1 0 4

출력 예시

---

1 1 0 0

#include <stdio.h>
#define MAXN (6)
int win[MAXN+10], lose[MAXN+10], draw[MAXN+10];
int sol[4+10];
 
int game[15][2];//15경기에 속한 두 나라 번호
void MakeGame(void){//대진표 작성
    int k=0;
    for (int a=0; a<5; a++){
        for (int b=a+1; b<6; b++){
            game[k][0]=a; game[k][1]=b; k++;
        }
    }
}
int DFS(int n){
    if (n >= 15) return 1;//15게임을 모두 통과했으므로 성공
    int a=game[n][0], b=game[n][1];
    //1.승패
    if (win[a] && lose[b]){
        win[a]--; lose[b]--;//표시
        if (DFS(n+1)) return 1;
        win[a]++; lose[b]++;//표시제거
    }
    //2.무무
    if (draw[a] && draw[b]){
        draw[a]--; draw[b]--;//표시
        if (DFS(n+1)) return 1;
        draw[a]++; draw[b]++;//표시제거
    }
    //3.패승
    if (lose[a] && win[b]){
        lose[a]--; win[b]--;//표시
        if (DFS(n+1)) return 1;
        lose[a]++; win[b]++;//표시제거
    }
    return 0;//실패
}
int Solve(void){
    //1.각 나라가 5게임을 했는 지 확인
    for (int i=0; i<6; i++){
        if (win[i] + draw[i] + lose[i] != 5) return 0;//불가능한 경우
    }
    //2.15게임 시뮬레이션
    return DFS(0);
}
 
void InputData(void){
    for (int i=0; i<MAXN; i++){
        scanf("%d %d %d", &win[i], &draw[i], &lose[i]);
    }
}
void OutputData(void){
    for (int i=0; i<4; i++){
        printf("%d ", sol[i]);
    }
    printf("\n");
}
int main(void){
    MakeGame();//대진표 작성
    for (int i=0; i<4; i++){
        InputData();// 입력받는 부분
        sol[i] = Solve();// 여기서부터 작성
    }
 
    OutputData();// 출력하는 부분
    return 0;
}