[백준][C++] 6987번: 월드컵 (263)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

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

6987번: 월드컵

 

1. 생각의 흐름

사실 보자마자 떠오른 방식은,

모든 팀은 게임을 할때마다 3가지 경우(승리, 비김, 패배)중 하나의 경우가 나온다 생각하였다.

 

또한 6개팀이 승부하는 경우의 수는 15가지 이다.

A: {B, C, D, E, F}

B: {C, D, E, F}

C: {D, E, F}

D: {E, F}

E: {F}

 

따라서 한 팀당 3번, 총 3^15 경우만 구해서 직접 가능한 case인지 확인해보면 될것이다.

brute force에 해당되는 방식이라 할 수 있다.

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

int input[6][3] = {0,};
int match[6][4] = {0,};
vector<int> vec(4);
int team1[] = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
int team2[] = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };

void DFS(int tc, int round) {
    if (round >= 15) {
        // 이미 가능한 경우로 판단된 경우
        if (vec[tc] == 1) return;

        for (int r = 0; r < 6; r++) {
            for (int c = 0; c < 3; c++) {
                if (match[r][c] != input[r][c])
                    return;
            }
        }

        vec[tc] = 1;
        return;
    }

    int team = team1[round];
    int other_team = team2[round];

    for (int j = 0; j < 3; j++) {
        match[team][j]++;
        match[other_team][2 - j]++;
        
        DFS(tc, round + 1);

        match[team][j]--;
        match[other_team][2 - j]--;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int t = 0; t < 4; t++) {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> input[i][j];
            }
        }
        DFS(t, 0);
    }

    for (int i = 0; i < 4; i++)
        cout << vec[i] << ' ';
    cout << "\n";

    return 0;
}