백준 6987번 월드컵 (C++)

문제 링크 : https://www.acmicpc.net/problem/6987

6987번: 월드컵

문제 요약

 

1. 6개의 팀이 서로 한 번씩 경기를 진행합니다. 승부의 결과는 승리 / 무승부 / 패배 3가지 입니다.

2. 4개의 테스트 케이스가 주어졌을때, (테스트 케이스 1줄 당 18개의 숫자가 입력됨) 해당 테스트 케이스가 가능한 경우인지 확인하세요.

3. 주어진 4개의 테스트에 대하여 가능한 경우 1을, 불가능한 경우 0을 공백을 한칸씩 띄고 출력하세요.

 

 

핵심 포인트

 

불가능한 조건들을 직접 나열할 경우 문제 풀이가 불가능합니다.

가령 승리와 패배의 갯수, 무승부의 갯수를 조건으로 나열하여 판별할 경우, 경우의 수가 너무 다양하여 예상치 못한 예외케이스가 발생합니다. 특히 무승부의 경우 조건을 나열하기가 까다롭습니다.

 

이 문제는 6개의 팀이 서로 경기를 치뤄 3개의 결과 중 하나를 얻을 수 있으므로,

완전탐색 - 백 트래킹으로 접근하면 시간복잡도는 O(3^15)가 나옵니다.

(한 경기당 3개의 결과, 총 15번의 경기)

 

 

문제 풀이

 

먼저 전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int arr[6][3], goal[6][3], ans[4];
vector<pair<int, int>> v;
bool res = true;

void backTracking(int depth) {
    if (depth == v.size()) {
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (arr[i][j] != goal[i][j]) return;
            }
        }
    }
    if (depth == v.size()) {
        res = false;
        return;
    }
    int a = v[depth].first, b = v[depth].second;
    // a 승
    arr[a][0]++;
    arr[b][2]++;
    backTracking(depth + 1);
    arr[a][0]--;
    arr[b][2]--;
    // 무승부
    arr[a][1]++;
    arr[b][1]++;
    backTracking(depth + 1);
    arr[a][1]--;
    arr[b][1]--;
    // b 승
    arr[a][2]++;
    arr[b][0]++;
    backTracking(depth + 1);
    arr[a][2]--;
    arr[b][0]--;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int cnt = 0;
    for (int i = 0; i < 6; i++) { // 1
        for (int j = i + 1; j < 6; j++) v.push_back({ i,j });
    }
    while (true) {
        res = true; // 2
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                arr[i][j] = 0;
                cin >> goal[i][j];
            }
        }
        backTracking(0); // 3
        if (!res) ans[cnt] = 1; // 4
        else ans[cnt] = 0;
        cnt++;
        if (cnt == 4) break;
    }
    for (int i = 0; i < 4; i++) cout << ans[i] << " ";
    return 0;
}

부분부분 쪼개어 설명을 진행하겠습니다.

 

1. 먼저 경기를 치루는 팀들의 값을 벡터에 저장합니다.

    for (int i = 0; i < 6; i++) { // 1
        for (int j = i + 1; j < 6; j++) v.push_back({ i,j });
    }

입력받는 값의 특성상 0부터 입력되었으나, 0이 아닌 1부터 시작한다고 가정했을때, 아래와 같은 값들이 입력됩니다.

 

1,2~1,6 (1번팀이 2번, 3번, 4번, 5번, 6번팀과 경기를 치룸)

2,3~1,6 (2번팀이 3번, 4번, 5번, 6번팀과 경기를 치룸)

...

5,6 (5번팀이 6번팀과 경기를 치룸)

 

총 15개의 경기가 입력됩니다.

 

2. 다음은 주어진 값이 가능한 경우인지 판단하기 위해 값을 입력하는 과정입니다.

 while (true) {
        res = true; // 1
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                arr[i][j] = 0; // 2
                cin >> goal[i][j]; // 3
            }
        }

(1) res가 true일 경우, 불가능한 경우입니다. false로 저장되면 가능한 경우입니다.

(2) arr[i][j]는 0으로 초기화합니다. 백트래킹을 진행하여 임시로 저장하는 값들입니다.

(3) 테스트하는 값을 입력받습니다.

 

3. 다음은 BackTracking 함수입니다.

void backTracking(int depth) {
    if (depth == v.size()) { // 2
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 3; j++) {
                if (arr[i][j] != goal[i][j]) return;
            }
        }
    }
    if (depth == v.size()) { // 3
        res = false;
        return;
    }
    int a = v[depth].first, b = v[depth].second; // 1
    // a 승
    arr[a][0]++;
    arr[b][2]++;
    backTracking(depth + 1);
    arr[a][0]--;
    arr[b][2]--;
    // 무승부
    arr[a][1]++;
    arr[b][1]++;
    backTracking(depth + 1);
    arr[a][1]--;
    arr[b][1]--;
    // b 승
    arr[a][2]++;
    arr[b][0]++;
    backTracking(depth + 1);
    arr[a][2]--;
    arr[b][0]--;
}

(1) 현재 경기를 치루는 팀의 값을 a,b에 각각 저장합니다. 

a가 승리 / 무승부 / 패배하는 경우들을 각각 입력하여 그 다음 경기로 backTracking을 진행합니다.

backTracking을 종료하고 return할 경우, 다시 arr배열의 값을 원래대로 되돌리는 과정을 잊으면 안됩니다.

 

(2) 현재 depth가 vector의 사이즈일경우, 모든 경기를 치뤘다는 뜻입니다.

goal[i][j]와 arr[i][j]가 하나라도 다르다면 입력받은 값은 현재 backTracking의 결과로는 나올 수 없다는 뜻이므로, 곧 바로 return을 합니다.

 

(3) 2번의 for문을 빠져나오고 3번에 도달했을 경우, 입력받은 값이 backTracking으로 나올 수 있는 값이라는 뜻이므로, res를 false로 바꾸고 return합니다.

 

4. BrackTracking을 종료하고 난 다음입니다.

	if (!res) ans[cnt] = 1; // 4
        else ans[cnt] = 0;
        cnt++;
        if (cnt == 4) break;
    }
    for (int i = 0; i < 4; i++) cout << ans[i] << " ";

res가 false인 경우가 가능한 케이스이고, res가 true인 경우에는 불가능한 케이스입니다. 

값을 올바르게 저장하고 4개의 케이스를 모두 테스트 했을 때 while문을 빠져나와 ans 배열의 값들을 출력하면 됩니다.