[SWEA] 1768 숫자야구게임

출처: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4su3xKXFUDFAUf&

 Input 

5

8975

6142

5047

1860

5419

 

 Output 

#1 6

#2 8

#3 7

#4 8

#5 7

total score = 100

total query = 36 

player2가 제시한 player1이 생각하는 수와 일치하는지는 0234~9876까지 완전탐색하며 확인할 수 있습니다.

하지만 그렇게 되면 일치하는지 확인하는 query 함수 호출은 최대 9876 - 0234번 필요합니다.

for (int i = 123; i <= 9876; ++i){
    if(isPossible(target))
        answer++;
}

중간에 중복된 숫자가 존재하는 경우 제외를 제외한다면 호출횟수는 줄어들것입니다.

DFS 탐색을 이용해서 중복없는 순열을 구성합니다.

num[] 배열에 중복되지 않는 4자리 숫자 저장

 

4자리 숫자 중 중복데이터를 제거하는 경우와 함께 보다 더 효율적인 방법이 있습니다.

바로 query() 결과로 이미 증면된 (실패) 숫자로 필터링 하는 것입니다.

if) 생각한 수 = 7654일 때, 추측 숫자 = 0123이라고 해봅시다.

- 일치하는 숫자가 없으므로 0123 →[Query 결과] ball = 0,.strike = 0 입니다.

   → data[0] = [0, 1, 2, 3, 0, 0]

- 다음 추측 숫자 = 3456 이라고 했을 때, 이 숫자를 Query 함수 호출하긴전에 data[]에 담긴 정보와 비교해봅니다.

   → ball = 1 → 실패 데이터에서 0~3까지는 생각한 수에 존재하지 않는데  0~3 중에 숫자가 1개 존재하므로

   query 함수를 호출하기 전에 필터링 해줍니다. (즉, 실패 데이터와 결과가 다르면 query 함수를 호출하지 않습니다.)

 

 4~9까지로 이루어진 숫자 4567과 비교하면 ball = 0, strike = 0으로 실패 데이터의 결과와 같으므로

   해당 추측 숫자를  query 함수로 실제 확인해봅니다. (성공하면 종료, 실패 시 실패 데이터 저장)

   ▶ 4자리 숫자 중 중복된 숫자 제거 (중복 없는 순열) + 실패 데이터 재활용한다면 최대 10번이내로 query 호출가능   

 

※ 유사 문제 풀이 참조

- [BOJ] 2503 숫자 야구 

[BOJ] 백준 2503 숫자 야구

- [Jungol] 3109 숫자 야구2 

[Jungol] 정올 3109 숫자 야구2

---

#define _CRT_SECURE_NO_WARNINGS
typedef struct {
    int strike;
    int ball;
} Result;
extern Result query(int supose[]);
//[0]~[3]:숫자,  [4]:스트라이크 개수,  [5]:볼 개수
int fail_data[10][6];
int dataCnt; // 검증된 데이터 개수
int* num;
int check[10];
int isPossible() {
    int i, j;
    for (i = 0; i < dataCnt; i++) {
        int strike = 0, ball = 0;
        for (j = 0; j <= 3; j++) {
            // 자리와 숫자가 일치하는 경우
            if (fail_data[i][j] == num[j]) strike++;
            // 자리는 다르지만 숫자가 동일하게 존재하는 경우
            else if (check[fail_data[i][j]]) ball++;
        }
        // strike 개수와 ball 개수가 완전히 일치하는지 확인
        // Query 호출하기전에 가지치기
        if ((fail_data[i][4] != strike) || (fail_data[i][5] != ball))
            return 0; 
    }
    return 1;
}
int DFS(int n) {
    int i;
    if (n >= 4) { // 중복 없는 4자리 숫자(0~9)
        // query 함수 호출전에 검증된 데이터로 1차 필터
        if (!isPossible())
            return 0;
        
        Result ret = query(num);
        if (ret.strike == 4)
            return 1; 
        
        // 검증된 실패 데이터 저장
        for (i = 0; i <= 3; i++)
            fail_data[dataCnt][i] = num[i];
        fail_data[dataCnt][4] = ret.strike; 
        fail_data[dataCnt][5] = ret.ball; 
        dataCnt++;
        
        return 0;
    }
 
    // 중복없는 순열 구현
    for (i = 0; i <= 9; i++) {
        if (check[i]) continue;
        num[n] = i; 
        check[i] = 1; // 사용 표시
        if (DFS(n + 1))
            // DFS 탐색 중간에 이미 성공한 경우
            return 1;
        check[i] = 0; // 표시 해제 
    }
    return 0; 
}
void doUserImplementation(int suppose[]) {
    num = suppose;
    dataCnt = 0;
    for (int i = 0; i <= 9; i++)
        check[i] = 0;
    DFS(0);
}