백준 15997. 승부 예측(C++)

15997. 승부예측

15997번: 승부 예측

---

입력

• 4 팀의 팀명이 주어진 후 각 경기별 정보가 주어진다.

---

문제 풀이

• 각 팀별 다음 라운드 진출확률을 구해야한다.

struct game			// 각 게임 정보 할당할 구조체
{
	string t1;		// A팀명
	string t2;		// B팀명
	double win1;	// A팀이 B팀에게 이길 확률
	double draw;	// A팀과 B팀이 비길 확률
	double win2;	// A팀이 B팀에게 질 확률
};

int n = 4;			// 팀 수

map<string, double>result;	// 각 팀별 다음 라운드에 진출할 확률 할당할 맵 (출력값)
map<string, int>score;		// 각 팀별 점수 기록할 맵
map<int, string>tnum;		// 각 팀에 번호를 부여해줄 수 있는 맵
vector<game>games;			// 게임 정보 받을 벡터

• 전역으로 선언한 변수이다.

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		score.insert(pair<string, int>(tmp, 0));	
        // 각 팀별 점수 0점으로 초기화
		tnum.insert(pair<int, string>(i, tmp));		
        // 주어진 순서대로 팀 번호 부여 (0~3)
	}

	for (int i = 0; i < n + 2; i++) {				
    // 게임 정보 할당 (총 6게임)
		game tmp;
		string team1, team2;
		double a, b, c;
		cin >> team1 >> team2 >> a >> b >> c;
		tmp.t1 = team1;
		tmp.t2 = team2;
		tmp.win1 = a;
		tmp.draw = b;
		tmp.win2 = c;
		games.push_back(tmp);
	}

	simul_game(0, 1.0);			
    // 첫 번째 인자는 진행 중인 경기 번호, 두 번째 인자는 일어날 확률

• 입력을 받은 후 dfs 구조를 가진 simul_game 함수로 결과를 도출했다.
• 함수의 구조는 다음과 같다.

void simul_game(int lv, double perc) { 
// lv - 현재 진행 중인 게임 번호, perc - 진행된 게임의 결과가 나올 확률
	if (perc == 0.0) {	
    // 만약 현재의 결과가 일어날 수 없는 경우라면 리턴
		return;
	}

	if (lv == n + 2) {	
    // 6 경기가 모두 진행되었다면, 다음 라운드 진출 팀 선정해야함
		vector<pair<int, int>>check;	
        // 팀 점수와 해당 팀 번호 저장할 벡터
		for (int i = 0; i < n; i++) {
			check.push_back(make_pair(score[tnum[i]], i)); 
		}
		sort(check.begin(), check.end()); 
        // 점수를 기준으로 오름차순 정렬
		int g1 = 1;		
        // 최고 점수로 올라갈 팀 수 1로 초기화 (동점 가능성 있음)
		int g2 = 0;		
        // 두 번째 점수로 올라갈 팀 수 0으로 초기화 (동점 가능성 있음)

		vector<int>gs1;	// 최고 점수로 올라갈 그룹
		vector<int>gs2;	// 두 번째 점수로 올라갈 그룹
		gs1.push_back(check[3].second);	
        // 오름차순으로 정렬했을 때 최고 점수 팀을 위에서 선언한 벡터에 추가
		for (int i = 2; i >= 0; i--) {
			if (check[i].first == check[3].first) {	
            // 최고 점수 팀과 같은 점수 팀이 있다면 
				g1 += 1;							
                // 최고 점수로 올라갈 팀 +1
				gs1.push_back(check[i].second);		
                // 추가
			}
			else {
				break;
			}

		}
		if (g1 < 2) {		
        // 만약 최고 점수 팀이 1팀이라면 두 번째 점수로 올라갈 팀을 선정해야함
			g2 = 1;			
            // 위와 같은 방식으로 진행
			gs2.push_back(check[n - g1 - 1].second);
			for (int i = n - g1 - 2; i >= 0; i--) {
				if (check[i].first == check[n - g1 - 1].first) {
					g2 += 1;
					gs2.push_back(check[i].second);
				}
				else {
					break;
				}
			}
		}
		if (g1 <= 2) {	
        // 최고 점수 팀이 2팀 이하라면 두 팀은 진출 확정
			for (int i = 0; i < g1; i++) {
				result[tnum[gs1[i]]] = result[tnum[gs1[i]]] + perc;	
                // 두 팀의 결과값에 현재 경우가 일어날 확률 perc 더해줌
			}
		}
		else {			
        // 최고 점수 팀이 3팀 이상이라면 추첨을 통해 두 팀 선정해야함
			for (int i = 0; i < g1; i++) {
				result[tnum[gs1[i]]] = result[tnum[gs1[i]]] + (double)(2 * perc / g1);	
				// 각 팀의 결과값에 2*(현재 경우 일어날 확률)/(최고 점수 팀 수)를 더함
			}
		}
		for (int i = 0; i < g2; i++) {	
        // 두 번째 점수로 올라가는 팀도 위와 같은 방식으로 결과값 더해줌
			result[tnum[gs2[i]]] = result[tnum[gs2[i]]] + (double)(perc / g2);
		}
		return;
	}


	for (int i = 0; i < 3; i++) {		
    // 경기별 3가지 경우
		if (i == 0) {					
        // A 팀이 이겼을 경우
			score[games[lv].t1] += 3;	
            // A 팀 점수 +3
			simul_game(lv + 1, perc * games[lv].win1);	
            // 다음 게임 진행 lv 에는 +1, perc 에는 해당 결과 일어날 확률 곱해줌
			score[games[lv].t1] -= 3;	
            // 다음 경우 따지기 위해 점수 복구
		}
		else if (i == 1) {				
        // 위와 같은 방식으로 진행
			score[games[lv].t1] += 1;
			score[games[lv].t2] += 1;
			simul_game(lv + 1, perc * games[lv].draw);
			score[games[lv].t1] -= 1;
			score[games[lv].t2] -= 1;
		}
		else {
			score[games[lv].t2] += 3;
			simul_game(lv + 1, perc * games[lv].win2);
			score[games[lv].t2] -= 3;
		}
	}
}

	for (int i = 0; i < n; i++) {		
		cout << fixed;
		cout.precision(10);	// 소숫점 10자리까지 고정적으로 출력되도록 설정
		cout << result[tnum[i]] << "\n";	// 각 팀별 결과값 출력
	}

• 조건에 맞게 출력