BaekJoon 15654번: N과 M (5)

간단한 문제지만 BackTracking을 사용하지 않는 경우 생각보다 시간이 오래 걸린다.

 

풀이법

1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다.

2) sort() 함수를 이용해서 오름차순으로 초기 배열을 정리해야 한다.

3) 방문한 곳을 다시 방문하지 않기 위한 visited 배열과 각 level의 값을 담을 수 있는 arr 배열을

   생각해 낸다면 어렵지 않게 풀 수 있는 문제이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> vec;
bool visited[10001];
int arr[9];
void backtracking(int level)
{
	if (level == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return; 
	}
	for (int i =0; i<vec.size(); i++)
	{
		if (visited[vec[i]])
		{
			continue;
		}
		visited[vec[i]] = true;
		arr[level] = vec[i];
		backtracking(level + 1);
		visited[vec[i]] = false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}
	sort(vec.begin(), vec.end());
	backtracking(0);
}

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest