[Silver 3] 15654번 N과 M (5)

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

15654번: N과 M (5)

 

이 문제는 DFS를 통한 백트레킹으로 해결할 수 있다.

 

알고리즘은 다음과 같다.

• vector에 N만큼의 입력 값을 삽입하고, 삽입이 끝나면 sort를 통해 오름차순으로 정렬한다.
• DFS를 0번 인덱스 부터 수행한다.
• 방문하지 않은 인덱스라면 방문 표시를 하고 cnt자리에 i번째 인덱스를 삽입한다. (DFS의 값)
• num은 필요하지 않은 값이지만 넣어버렸다.(실수)

 

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int arr[9] = { 0, };
int visited[9] = { 0, };
vector<int> graph;

void dfs(int num, int cnt)
{
    if (cnt == M)
    {
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 0; i < N; i++)
    {
        if (!visited[i]) {
            visited[i] = 1;
            arr[cnt] = graph[i];
            dfs(i + 1, cnt + 1);
            visited[i] = 0;
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int value;
        cin >> value;
        graph.push_back(value);
    }
    sort(graph.begin(), graph.end());
    dfs(0, 0);
}