[백준 - 2503] 숫자 야구 [C++]

1. 문제

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

2503번: 숫자 야구

2. 풀이과정

1. 서로 다른 숫자 세 개로 구성된 세 자리 수를 생성한다.

2. 해당 숫자가 문제에서 주어진 모든 질문&답에 부합하는지 검사한다.

 

1~2를 가능한 세 자리 수들에 대해 전부 반복한다.

[코드설명]

dfs함수는 서로 다른 숫자 세 개로 구성된 세 자리 수를 생성해준다.

1 2 3

1 2 4

1 2 5

   .

   .

9 8 7

순으로 생성한다.

 

check함수는 숫자가 문제에서 주어진 모든 질문&답에 부합하는지 검사한다.

 

3. 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;
int n;
vector<vector<int>> questions;
bool visited[10];
int result;

bool check(vector<int>& nums) {
    string num = to_string(nums[0]*100 + nums[1]*10 + nums[2]);
    for(int j=0; j<n; j++) {
        string key = to_string(questions[j][0]);
        int strike = 0, ball = 0;
        for(int k=0; k<3; k++) {
            if(num[k] == key[k]) strike++;
            for(int h=0; h<3; h++) {
                if(h!=k && key[h]==num[k]) ball++;
            }
        }
        if(strike != questions[j][1] || ball != questions[j][2]) return false;
    }
    return true;
}

void dfs(vector<int>& nums, int depth) {
    if(depth == 3) {
        if(check(nums)) result++;
        return ;
    }
    for(int i=1; i<=9; i++) {
        if(!visited[i]) {
            nums.push_back(i);
            visited[i] = true;
            dfs(nums, depth+1);
            nums.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    questions.resize(n);
    for(int i=0; i<n; i++) {
        int question, strike, ball;
        cin >> question >> strike >> ball;
        questions[i].push_back(question);
        questions[i].push_back(strike);
        questions[i].push_back(ball);
    }
    vector<int> nums;
    dfs(nums, 0);
    cout << result;
    return 0;
}