[Algorithm]Baekjoon 6987번 : 월드컵

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
 
using namespace std;
 
 
bool results[4] = { false };
int arr[4][6][3];
int curMatch[6][3] = { 0 };
 
void CheckResults()
{
    for (int i = 0; i < 4; ++i)
    {
        if (!results[i])
        {
            bool isBreak = false;
            
            for (int j = 0; j < 6; ++j)
            {
                for (int k = 0; k < 3; ++k)
                {
                    if (arr[i][j][k] != curMatch[j][k])
                    {
                        isBreak = true;
                        break;
                    }
                }
 
                if (isBreak) break;
            }
 
            if (!isBreak)
            {
                results[i] = true;
            }
        }
    }
}
 
const int team1[] = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4 };
const int team2[] = { 1, 2, 3, 4, 5, 2, 3, 4, 5, 3, 4, 5, 4, 5, 5 };
 
void DFS(const int round)
{
    if (round == 15) // 모든 경기를 끝냄.
    {
        CheckResults();
        return;
    }
 
    const int firstTeam = team1[round];
    const int secondTeam = team2[round];
        
 
    // 이긴경우
    curMatch[firstTeam][0]++;
    curMatch[secondTeam][2]++;
    DFS(round+1);
    curMatch[firstTeam][0]--;
    curMatch[secondTeam][2]--;
 
 
    // 무승부
    curMatch[firstTeam][1]++;
    curMatch[secondTeam][1]++;
    DFS(round+1);
    curMatch[firstTeam][1]--;
    curMatch[secondTeam][1]--;
 
 
    // 패배
    curMatch[firstTeam][2]++;
    curMatch[secondTeam][0]++;
    DFS(round+1);
    curMatch[firstTeam][2]--;
    curMatch[secondTeam][0]--;
        
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 4; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cin >> arr[i][j][0] >> arr[i][j][1] >> arr[i][j][2];
        }
    }
 
    DFS(0);
    
    for (int i = 0; i < 4; ++i)
    {
        cout << results[i] << ' ';
    }
 
    return 0;
}
 
 

 

 

아... 저렇게 각팀의 경기를 team1, team2로 저장해서 진행하는 것을 생각 못했다.

생각보다 오래걸린문제. 

 

저걸 생각못했을 때는 탐색을 어떻게 진행해야하나? 고민을 많이 했는데.. 덕분에 또 배우고 간다.