[DFS] 6987번 월드컵

6987번 월드컵

 

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

 

문제

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

!!!

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

 

입력

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

 

출력

입력에서 주어진 네 가지 결과에 대하여 가능한 결과는 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

 

해결방법

DFS + 백트래킹을 통해 모든 경우를 다해보는 완전 탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

완전탐색 문제라는 사실은 알았는데 구현을 하는 부분이 헷갈려서 애를 먹었다

재귀는 정말 많은 연습이 필요할것 같다...

 

전체 경기는 아래와 같이 총 15번 진행된다

A 𝙫𝘀 B C D E F

B 𝙫𝘀 C D E F

C 𝙫𝘀 D E F

D 𝙫𝘀 E F

E 𝙫𝘀 F

 

또한 각 경기는 3가지 경우가 존재한다

• Team1 승리 , Team2 패배
• Team1 비김 , Team2 비김
• Team1 패배 , Team2 승리

 

이때 시간복잡도는 O(3^15) = 14,348,907 로 완전탐색을 진행할 수 있다

결과적으로 DFS + 백트래킹을 통해 모든 경우를 탐색할 수 있다

 

 

 

소스코드

문제 해결 시간 : 1h 30m

메모리 : 1988 KB

시간 : 116 ms

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

int team1[15] = {0,0,0,0,0,1,1,1,1,2,2,2,3,3,4};
int team2[15] = {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};

int a[4][6][3];
int result[6][3];
int ans[4];

void dfs(int game){
    // 모든 경기를 마쳤다면
    if(game == 15){
        for(int t=0; t<4; t++){
            // 이미 존재하는 경우로 판별됐다면
            if(ans[t]==1) continue;
            
            bool flag = true;
            for(int i=0; i<6; i++){
                for(int j=0; j<3; j++){
                    if(a[t][i][j] != result[i][j]){
                        flag = false;
                        break;
                    }
                }
                if(!flag) break;
            }
            
            // 경기결과가 일치한다면
            if(flag){
                ans[t] = 1;
                return;
            }
        }
        
        return;
    }
    
    int t1 = team1[game];
    int t2 = team2[game];
    
    // t1 win, t2 lose
    result[t1][0]++;
    result[t2][2]++;
    dfs(game+1);
    result[t1][0]--;
    result[t2][2]--;
    
    // t1 draw, t2 draw
    result[t1][1]++;
    result[t2][1]++;
    dfs(game+1);
    result[t1][1]--;
    result[t2][1]--;
    
    // t1 lose, t2 win
    result[t1][2]++;
    result[t2][0]++;
    dfs(game+1);
    result[t1][2]--;
    result[t2][0]--;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int t=0; t<4; t++){
        for(int i=0; i<6; i++){
            for(int j=0; j<3; j++){
                cin >> a[t][i][j];
            }
        }
    }
    
    dfs(0);
    
    for(int i=0; i<4; i++){
        cout << ans[i] << " ";
    }
    cout << "\n";
    
    return 0;
}