[Jungol] 정올 1847 월드컵

 

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1114&sca=4030

Approach

[BOJ] 6987 월드컵 문제 참고

[BOJ] 백준 6987 월드컵

승리 횟수: 5 + 3 + 2 + 2 + 0 + 1 = 13

패배 횟수: 0 + 1 + 2 + 3 + 5 + 4 = 15

누군가가 이기면 다른 누군가는 지는 승부이기 때문에 승/패가 맞지 않습니다.

단순히 승/무/패 합을 비교하는 등을 통해서는 문제를 풀기 쉽지 않습니다.

문제조건상 6개국에 대한 네 가지의 결과가 주어지므로 완전탐색으로 접근

 

▶ 대전표

    [0]: 1 ~ 5

    [1]: 2 ~ 5

    [2]: 3 ~ 5

    [3]: 4 ~ 5

    [4]: 5　

 

즉, [0] vs [1] 승부에 대해서 3가지 결과에서 가능한 결과만 계속해서 탐색합니다. (DFS)

    → win | lose

    → lose | win

    → draw | draw 

---

#include <stdio.h>
 
int tc = 4, arr[6][3], sum;
void input() {
    int i, j;
    for (i = 0; i < 6; ++i) {
        for (j = 0; j < 3; ++j) {
            scanf("%d", arr[i] + j);
            sum += arr[i][j];
        }
    }
}
 
int DFS(int x, int y, int sum) {
    // 모든 팀의 경기가 끝난 경우
    if (x > 4)
        return sum == 0;
    // 특정 한 팀을 기준으로 경기가 끝났다면 다른 팀을 기준으로 잡아서 탐색
    if (y > 5)
        return DFS(x + 1, x + 2, sum);
    
    // 승, 무, 패
    for (int j = 0; j < 3; ++j) {
        if (arr[x][j] && arr[y][2 - j]) {
            arr[x][j]--, arr[y][2 - j]--;
            
            if (DFS(x, y + 1, sum - 2)) {
                return 1;
            }
 
            arr[x][j]++, arr[y][2 - j]++;
        }
    }
 
    return 0;
}
 
int main() {
    while (tc--) {
        sum = 0;
        input();
        int res = DFS(0, 1, sum);
        printf("%d ", res);
    }
    return 0;
}