[Algorithm] Baekjoon 15664번 : N과 M (10)

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

15664번: N과 M (10)

int n, m;
vector<int> nums;
vector<int> v;
 
void DFS(int curIndex)
{
    if (v.size() == m)
    {
        for (int i = 0; i < m; ++i)
        {
            printf("%d ", v[i]);
        }
        printf("\n");
 
        return;
    }
 
    bool visited[10001] = { false };
 
    for (int i = curIndex + 1; i < n; ++i)
    {
        if (visited[nums[i]]) continue;
 
        visited[nums[i]] = true;
        v.push_back(nums[i]);
        DFS(i);
        v.pop_back();
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        int temp = 0;
        cin >> temp;
        nums.push_back(temp);
    }
 
    sort(nums.begin(), nums.end());
 
    bool visited[10001] = { false };
 
    for (int i = 0; i < n; ++i)
    {
        if (visited[nums[i]]) continue;
 
        visited[nums[i]] = true;
        v.push_back(nums[i]);
        DFS(i);
        v.pop_back();
    }
}

기본적으로 '비 내림차순'이며, 문제에 명시되어 있진 않지만 같은 구성의 수열에 대해 순서가 다르더라도 같은 가짓수로 친다.

즉, 1,9와 9,1은 같은걸로 치기때문에 1,9가 출력되었다면 9,1은 출력되면 안된다.

그리고 중복된 수열도 출력하면 안된다. 그렇기때문에 각 depth마다 사용되는 정수값이 중복되어서는 안된다.

그래서 각 depth마다 visited를 선언해서 해당 depth에서 사용된 정수값을 체크한다.

이미 사용된걸 사용하면 중복된 수열이 발생할 수 있기 때문에 반드시 막아줘야 한다.