[DFS 순열] SWEA 1768 숫자 야구 게임 C++

※ 문제

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

SW Expert Academy

 

※ 풀이

1) DFS로 0~9까지의 숫자를 중복 없이 사용한 4자리 숫자를 전부 미리 저장합니다. 저는 직접 연결리스트로 구현해 저장하였습니다.

2) query() 함수를 실행한 후, 얻은 strike와 ball의 정보로 위에서 구한 숫자 중 불가능한 숫자들을 제거합니다. 이를 위해 나만의 쿼리 함수 findNot()을 만들어 사용합니다.

3) 위의 과정을 반복하여 실행합니다.

 

혹은 실패 정보들을 전부 저장하여 DFS로 숫자를 구할 때마다 제거하는 방식도 있습니다.

#define N 4
#define MAXN 10000

typedef struct {
    int strike;
    int ball;
} Result;
 
// API
extern Result query(int guess[]);

struct Node{
    int idx=-1;
    int data[4]; // 4자리 숫자 저장
    Node* next;
};

bool visited[10]; // 0~9까지 방문 여부
int four[N];
int bufferCnt;
Node node[MAXN];
Node head, tail;

void init() {
    bufferCnt=0;
    head.next=&tail;
}

Node* getNode() {
    node[bufferCnt].idx = 0;
    for(int i=0; i<N; i++) node[bufferCnt].data[i] = four[i];
    node[bufferCnt].next = nullptr;
    return &node[bufferCnt++];
}

void addNode() {
    Node* ptr = &head;
    Node* temp = getNode();
    while(ptr->next->idx!=-1) ptr = ptr->next; // 맨 뒤 삽입, head 존재하므로 next 확인
    temp->next = ptr->next;
    ptr->next = temp;
}

void dfs(int depth) {
    if (depth == N) {
        addNode(); // 4자리 가능한 숫자 모두 저장
        return;
    }
    
    for(int i=0; i<10; i++) {
        if (visited[i]) continue;
        visited[i] = 1;
        four[depth] = i;
        dfs(depth+1);
        visited[i] = 0;
    }
}

void findNot(int guess[], Result res) {
    Node* ptr = &head;
    while(ptr->next->idx!=-1) {
        int strike=0, ball=0;
        int num[10]={0,0,0,0,0,0,0,0,0,0};
        for (int i=0; i<N; i++) num[guess[i]]++; // ball 계산

        for(int i=0; i<N; i++) {
            if (guess[i] == ptr->next->data[i]) strike++;
            else if (num[ptr->next->data[i]]>0) ball++;
        }
        
        if ((res.strike != strike) || (res.ball != ball)) { // strike 혹은 ball 다르면 삭제
            ptr->next = ptr->next->next;
            bufferCnt--;
        }
        else ptr=ptr->next;
    }
}

void doUserImplementation(int guess[]) { // 배열 주소 받아 사용
    for(int i=0; i<10; i++) visited[i] = false; // visited 초기화
    init();
    dfs(0); // 4자리 숫자 중복 없는 순열
    
    Node* ptr = &head;
    while (bufferCnt>1) {
        for (int i = 0; i < N; i++) guess[i] = (&head)->next->data[i];
        Result res = query(guess); // 4자리 숫자 쿼리
        if (res.strike == N) break; // 스트라이크 4개 종료

        findNot(guess, res); // 위의 쿼리 정보로 불가능한 숫자 제거(나만의 쿼리 함수)
    }
    
    for (int i = 0; i < N; i++) guess[i] = (&head)->next->data[i];
}