백준 6987: 월드컵(c++, 백트래킹)

사용 언어	티어	시간 제한	메모리 제한
c++		1초	128MB

 

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

6987번: 월드컵

 

#0 문제

월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부, 패의 수가 가능한 결과인지를 판별하려고 한다. 다음은 가능한 결과와 가능하지 않은 결과의 예이다. 네 가지의 결과가 주어질 때 각각의 결과에 대하여 가능하면 1, 불가능하면 0을 출력하는 프로그램을 작성하시오.

 

#1 입력

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

 

#2 접근

• 4개의 예제에 대해서 가능한 결과인지 아닌지 판단하는 문제이다.
• 6팀으로 정해져있고, 리그 방식으로 진행하므로, 총 경기 일정은 $_{6}C_{2} = 15$ 가지이다.
• 승, 무, 패 3가지의 경우가 있으므로 모든 가능한 결과의 경우의 수는 $3^{15} = 14348907 \approx 10^{7}$ 이므로 충분히 계산 가능하다.
• 백트래킹을 통해 전체 경우의 수를 탐색해보면서 가능한지 여부를 판단하도록 한다.

 

#3 풀이

• 모든 경기 일정의 조합은 15가지이므로 해당하는 comb 배열을 만들어준다.
• 백트래킹을 통해 문제를 해결한다.
  • num 번째 예시에 대해 결과가 맞다고 판별났으면 더이상 탐색할 필요가 없으므로 종료한다.
  • 15번째 경기까지 치뤘을 경우, 지금 가지고 있는 스코어 보드와 예시의 스코어 보드를 비교해보고 다른 것이 하나라도 있으면 종료하고, 전체 다 맞을 경우 결과가 맞다고 판별한다.
  • 각각 승, 무, 패에 대해 스코어 보드를 바꾸어주고 백트래킹을 호출한다. 호출 후 스코어 보드는 원상태로 복귀시킨다.

 

#4 코드

/*
6987 월드컵
백트래킹
*/

#include <iostream>
#include <string>
#include <vector>
#include <cstring>


using namespace std;

typedef pair<int, int> P;

P comb[15] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}};

// 승 무 패
int score1[3] = {0, 1, 2};
// 패 승 무
int score2[3] = {2, 1, 0};

int board[6][3];
int ex[4][6][3];
int ans[4];



void backtracking(int idx, int num) {
    if (ans[num]) return;
    if (idx == 15) {
        for (int i = 0; i < 6; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (ex[num][i][j] != board[i][j]) {
                    return;
                }
            }
        }
        ans[num] = 1;
        return;
    }

    int a = comb[idx].first;
    int b = comb[idx].second;

    for (int i = 0; i < 3; ++i) {
        board[a][score1[i]]++;
        board[b][score2[i]]++;
        backtracking(idx + 1, num);
        board[a][score1[i]]--;
        board[b][score2[i]]--;
    }
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 6; ++j) {
            // 승 무 패
            for (int k = 0; k < 3; ++k) {
                cin >> ex[i][j][k];
            }
        }
    }

    for (int i = 0; i < 4; ++i) {
        backtracking(0, i);
    }



    for (int i = 0; i < 4; ++i) {
        cout << ans[i] << " ";
    }

    return 0;
}