C++로 만드는 숫자 야구 게임 : 문제를 푸는 알고리듬

 이전 글에서는 초록이(문제를 내는 알고리듬)를 만들었으니 이번엔 파랑이를 만들어 주려고 합니다.

2021.03.29 - [Program Language and Algorithm] - C++로 만드는 숫자 야구 게임 : 문제를 내는 알고리즘

C++로 만드는 숫자 야구 게임 : 문제를 내는 알고리즘

 초록이는 간단했지만 파랑이는 조금 복잡합니다. 쉽게 만들면 쉽고 어렵게 만들면 어렵죠. 일단 가장 간단한 방법으로 만들어 보았습니다.

 초록이는 문제를 내고, 검사 하고, 통보하는 게임의 심판과 같은 역할이라면, 파랑이는 정답을 추측하는 역할입니다. 이런 파랑이를 어떻게 만들까요?

 플레이어에 따라 다르겠지만 제가 이 게임을 해결하는 방법은 이렇습니다. 추론했던 숫자 조합과 초록이가 준 결과를 보고 확률적으로 다음 숫자를 추론합니다. 여러 번의 추론과 결과를 누적해서 모든 결과에 논리적으로 부합하는 새로운 조합을 추론합니다. 이 방법을 파랑이에게 알려주려 하니 막막합니다. 추론한 데이터와 결과 들을 조합해서 새로운 조합을 만드는 알고리듬은 제가 제일 싫어하는 확률이라서 다른 방법을 이용하겠습니다.

 다행(?!)스럽게 파랑이는 컴퓨터 소프트웨어 입니다. 사람은 720개(3개의 숫자 10 * 9 * 8)의 경우의 수를 관리하는 게 현실적으로 어렵지만 컴퓨터에겐 쉽습니다. 그래서 불명확한 숫자 30개를 다루며, 확률적인 추론을 하는 것보다 720개의 경우의 수를 줄여 가는 구조가 더 쉽습니다. 그래서 아래와 같은 기능으로 동작합니다.

• 모든 후보군을 생성한다.
• 초록이의 결과와 후보군을 비교하여 후보군을 추린다.

 위 작업을 반복해서 후보군을 줄여가면, 결과에 도달할 수 있습니다. 그럼 첫 번째 후보군 생성 함수를 만들어 보죠. 아래 예제는 쉽게 제작한 후보군 생성 함수입니다.

// 후보군을 만드는 함수
// cand : 후보군 저장
// dL : 숫자수.
void makeCand(vector<vector<int>> &cand, int dL){
    for(int i = 0 ; 10 > i ; i++){
	for(int j = 0 ; 10 > j ; j++){
	    if(i == j){
		continue;
	    }
	    for(int k = 0 ; 10 > k ; k++){
		if(i == k || j == k){
		    continue;
		}
		if(3 == dL){
		    cand.push_back(vector<int>{i,j,k});
		}else{
		    for(int l = 0 ; 10 > l ; l++){
			if(i == l || j == l || k == l){
			    continue;
			}
			cand.push_back(vector<int>{i,j,k,l});
		    }
		    
		}
	    }
	}
    }
}

 이 함수는 복잡한 소프트웨어 엔지니어링 기술이 없어도 만들 수 있는 다중 반복문을 이용합니다. 사실 이 함수만 3가지 버전으로 제작했는데 그중 가장 기술 사용이 적은 함수를 소개해 드립니다. (동시에 확장성도 낮습니다.) 이 함수를 만드는 방법으로만 향후 글 하나를 작성하려 합니다. 그때 이 부분은 삭제되고, 링크가 남겠죠. 이 함수를 만드는 다양한 방법은 다음 글을 참조해 주시기 바랍니다.

2021.04.02 - [Program Language and Algorithm] - 중복 없는 수열 만드는 알고리즘 ( C++로 만드는 숫자 야구 게임 )

중복 없는 수열 만드는 알고리즘 ( C++로 만드는 숫자 야구 게임 )

 딱히 주석 등의 설명은 붙이지 않았습니다. 이유는 단순하니까요. 반복문과 조건문만 이용되었으며, 특이 점으로는 dL이 3일 때와 4일 때의 분기를 나누어 둔 것이죠. ( 그렇습니다. 초록이는 dL의 크기가 더 커도 동작하지만 파랑이의 이 함수는 안됩니다. + 향후 기재할 다른 함수에서는 해결 합니다. ) 그래서 dL이 3 일때와 4 일때의 후보군을 cand에 생성해 줍니다.

 두 번째는 후보군을 추리는 함수입니다. 이 함수는  모든 후보군과 추론한 조합을 비교해서 결과( X 스트라이크, Y 볼)를 획득합니다. 이 결과와 초록이의 결과를 비교해서 똑같은 후보군은 남기고, 나머지는 삭제합니다. 그리고 추론한 후보군을 삭제 합니다. (재사용할 이유가 없습니다.) 함수는 두 개의 함수로 구성됩니다. 하나는 두 후보군(하나는 추론한 후보군)을 비교한 결과를 얻고, 하나는 후보군을 추립니다.

// 정답 검사
// jud : 결과
// in : 입력
// ans : 정답
// dL : 난이도
void judge(vector<int> &jud, vector<int> &in, vector<int> &ans, int dL){
    // strike
    jud[0] = 0;
    // ball
    jud[1] = 0;

    // 단순 비교를 통한 결과 계산.
    for(int i = 0 ; dL > i ; i++){
	for(int j = 0 ; dL > j ; j++){
	    if(ans[i] == in[j]){
		if(i == j){
		    jud[0]++;
		}else{
		    jud[1]++;
		}
	    }
	}
    }
}

// 후보 추리기 : 추측한 답과 후보들과의 정답 판정을 통해. 초록이가 해준 판정과 같으면 유지. 아니면 삭제
// cand : 정답 후보
// jud : 초록이의 판정
// iIdx : 추측했던 후보 idx
// dL : 난이도
void removeCand(vector<vector<int>> &cand, vector<int> jud, int iIdx, int dL){
    // 각 후보자의 삭제 여부 : false 삭제, true 유지
    vector<bool> cs(cand.size(), false);

    // 후보와 추측의 비교 결과 저장
    vector<int> iJud(2);

    // 모든 후보군에 대해서 추측 값과의 정답을 얻어 초록이의 판정과 비교 : 같은 경우 cs[i] = true
    for(int i = 0 ; cand.size() > i ; i++){
	judge(iJud, cand[i], cand[iIdx], dL);

	if(iJud[0] == jud[0] && iJud[1] == jud[1]){
	    cs[i] = true;
	}
    }

    // cs가 true인 경우를 남기고 전체 삭제. 방금 이용한 후보도 삭제.
    cs[iIdx] = false;

    int idx = 0;
    for(int i = 0 ; cand.size() > i ; i++){
	if(cs[i]){
	    for(int j = 0 ; dL > j ; j++){
		cand[idx][j] = cand[i][j];
	    }
	    idx++;
	}
    }

    cand.erase(cand.begin()+ idx, cand.end());
}

 이미 주석으로 코드에 대한 설명은 모두 했습니다. 그런데 후보를 삭제하는 부분은 주석으로 남기기엔 너무 길어져서, 아래에 설명합니다. 벡터에서 중간에 있는 원소를 제거하는 것은 어려운 작업은 아니지만, 리소스 소모가 큽니다. 이유는 벡터의 구조 때문 입니다. 벡터의 모든 원소는 연속된 저장 공간에 위치합니다. 만약 원소 하나가 중간에서 사라지면, 그 뒤에 있는 원소들은 해당 원소의 자리를 채우기 위해 이동해야 합니다. 이러한 구조로 인해 벡터에서 원소의 삭제는 많은 리소스를 필요로 합니다. 그런데 위 함수에서 원소를 하나씩 제거하는 작업은 소프트웨어의 종료까지 최대 719회 (dL = 3 기준) 발생하게 되죠. 이걸 매번 해주는 건 효율적이지 않습니다. 그래서 제가 이용한 방법은 벡터에 데이터를 갱신하는 것입니다. cs가 false인 원소는 어차피 삭제해야 할 원소이고, true인 원소만 유지하면 됩니다. 그러니 후보군의 모든 원소를 순회하며, cs가 true인 원소만 0번째 자리부터 채워 나가는 거죠. 이 연산을 끝까지 하고 나면, 벡터의 0부터 idx-1까지의 데이터만 유지하고, 나머진 삭제할 원소입니다. erase 함수를 이용해 쉽게 제거합니다.

 마지막으로 메인 함수입니다. 이번에도 주석으로 필요한 설명은 해두었습니다. 정답 추측은 그냥 난수를 발생시켜 남아있는 후보군에서 선택합니다.

int main(int argc, char ** argv){
    // 난수 발생 초기화
    srand(time(nullptr));

    cout << "Enter the defficulty level (3 or 4) : ";

    // 난이도 입력
    int dL;
    cin >> dL;

    // 후보군 저장
    vector<vector<int>> cand;
    // 초록이의 판정
    vector<int> jud(2);

    // 후보군 생성
    makeCand(cand, dL);

    while(0 < cand.size()){
	// 추측하는 정답은 난수로 결정.
	int idx = rand() % cand.size();

	// 추측 값 출력.
	for(int i = 0 ; dL > i ; i++){
	    cout << cand[idx][i] << " ";
	}
	cout << endl;

	// 결과 수집. 스트라이크 and 볼
	cin >> jud[0];
	cin >> jud[1];

	// 종료 조건. 정답..
	if(dL == jud[0]){
	    break;
	}

	// 후보군 정리.
	removeCand(cand, jud, idx, dL);
    }

    return 0;
}

 초록이를 구현한 소프트웨어와 다른 점 느끼셨나요? 초록이는 친절했지만 파랑이는 친절하지 않습니다. 이유는 제가 귀찮아서가 아니에요. 누가 이 소프트웨어와 놀고 싶겠어요. 초록이랑 놀 때는 초록이가 만든 정답을 3아웃 당하지 않고 9회의 조건안에 찾아야하니 도전의식이 생기 겠지만...파랑이랑 놀때는 플레이어가 정답을 만들고, 추론을  정답과 비교해서 스트라이크와 볼을 계산해 알려주어야 합니다. 그리고 파랑이는 특별한 이변이 없는 한 항상 맞춥니다. 어차피 소프트웨어의 제작자와 디버거 외에는 호기심으로나 한두 번 플레이할 소프트웨어이니 친절하지 않게 만들었습니다.

 그럼 이제 소프트웨어의 전체 코드와 스냅숏을 보여드리겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// 후보군을 만드는 함수
// cand : 후보군 저장
// dL : 숫자수.
void makeCand(vector<vector<int>> &cand, int dL){
    for(int i = 0 ; 10 > i ; i++){
	for(int j = 0 ; 10 > j ; j++){
	    if(i == j){
		continue;
	    }
	    for(int k = 0 ; 10 > k ; k++){
		if(i == k || j == k){
		    continue;
		}
		if(3 == dL){
		    cand.push_back(vector<int>{i,j,k});
		}else{
		    for(int l = 0 ; 10 > l ; l++){
			if(i == l || j == l || k == l){
			    continue;
			}
			cand.push_back(vector<int>{i,j,k,l});
		    }
		    
		}
	    }
	}
    }
}

// 정답 검사
// jud : 결과
// in : 입력
// ans : 정답
// dL : 난이도
void judge(vector<int> &jud, vector<int> &in, vector<int> &ans, int dL){
    // strike
    jud[0] = 0;
    // ball
    jud[1] = 0;

    // 단순 비교를 통한 결과 계산.
    for(int i = 0 ; dL > i ; i++){
	for(int j = 0 ; dL > j ; j++){
	    if(ans[i] == in[j]){
		if(i == j){
		    jud[0]++;
		}else{
		    jud[1]++;
		}
	    }
	}
    }
}

// 후보 추리기 : 추측한 답과 후보들과의 정답 판정을 통해. 초록이가 해준 판정과 같으면 유지. 아니면 삭제
// cand : 정답 후보
// jud : 초록이의 판정
// iIdx : 추측했던 후보 idx
// dL : 난이도
void removeCand(vector<vector<int>> &cand, vector<int> jud, int iIdx, int dL){
    // 각 후보자의 삭제 여부 : false 삭제, true 유지
    vector<bool> cs(cand.size(), false);

    // 후보와 추측의 비교 결과 저장
    vector<int> iJud(2);

    // 모든 후보군에 대해서 추측 값과의 정답을 얻어 초록이의 판정과 비교 : 같은 경우 cs[i] = true
    for(int i = 0 ; cand.size() > i ; i++){
	judge(iJud, cand[i], cand[iIdx], dL);

	if(iJud[0] == jud[0] && iJud[1] == jud[1]){
	    cs[i] = true;
	}
    }

    // cs가 true인 경우를 남기고 전체 삭제. 방금 이용한 후보도 삭제.
    cs[iIdx] = false;

    int idx = 0;
    for(int i = 0 ; cand.size() > i ; i++){
	if(cs[i]){
	    for(int j = 0 ; dL > j ; j++){
		cand[idx][j] = cand[i][j];
	    }
	    idx++;
	}
    }

    cand.erase(cand.begin()+ idx, cand.end());

}

int main(int argc, char ** argv){
    // 난수 발생 초기화
    srand(time(nullptr));

    cout << "Enter the defficulty level (3 or 4) : ";

    // 난이도 입력
    int dL;
    cin >> dL;

    // 후보군 저장
    vector<vector<int>> cand;
    // 초록이의 판정
    vector<int> jud(2);

    // 후보군 생성
    makeCand(cand, dL);

    while(0 < cand.size()){
	// 추측하는 정답은 난수로 결정.
	int idx = rand() % cand.size();

	// 추측 값 출력.
	for(int i = 0 ; dL > i ; i++){
	    cout << cand[idx][i] << " ";
	}
	cout << endl;

	// 결과 수집. 스트라이크 and 볼
	cin >> jud[0];
	cin >> jud[1];

	// 종료 조건. 정답..
	if(dL == jud[0]){
	    break;
	}

	// 후보군 정리.
	removeCand(cand, jud, idx, dL);
    }

    return 0;
}

스냅숏에 이용한 예제는 첫 번째에 dL 3와 7 9 2이고, 두 번째는 dL 4와 8 9 1 4입니다.

 이상으로 파랑이의 구현을 마쳤습니다. 위에도 기재했지만 후보군을 만드는 함수는 여러 방식으로 만들어 두었기에, 다음 글은 후보군을 만드는 함수와 거기에 들어간 자료구조, 소프트웨어 엔지니어링 기술 들에 대해 쓰게 될 것 같습니다.

 

긴 글 봐주셔서 감사합니다.