[BOJ] 15649. N과 M (1)

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (baekjoon)

백준 사이트에 있는 N과 M 시리즈는 백트래킹, DFS의 기본을 다지기 좋다.

1부터 12까지 한번 쭉 풀어봤지만 다시 한번 풀어보며 포스팅을 해보려고 한다.

 

우선 N과 M 시리즈를 풀기 전에 순열과 조합에 대한 개념을 알아둬야 한다.

순열이란 순서가 상관이 있는 모임이다.

순열에 있어서 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}은 모두 다른 것으로 취급된다.

조합은 순서가 상관이 없는 모임이다.

조합에 있어서 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}은 모두 같은 것으로 취급된다.

그러므로 1, 2, 3으로 이루어진 순열의 개수는 6개이고, 조합의 개수는 1개이다.

 

---

 

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

15649번: N과 M (1)

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

int N, M;
int visited[8];		// 방문 여부를 관리할 배열
vector<int> series;	// M개의 수를 골라 만든 수열을 저장할 벡터
void dfs(int cnt);		// M개의 수를 골라 수열을 만드는 함수
void print();			// 만든 수열을 출력하는 함수

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> N >> M;
	dfs(0);
	return 0;
}

void dfs(int cnt) {
	if (cnt == M) {	// M개를 고르면 수열 출력
		print();
		return;
	}

	for (int i = 0; i < N; i++) {
		if (!visited[i]) {	// 중복없이 골라야 하므로 방문하지 않은 수만 탐색
			visited[i] = true;
			series.push_back(i + 1);
			dfs(cnt + 1);
			// 해당 수에 대한 탐색이 끝났으므로 방문 여부를 false로 바꾸고 vector에서도 삭제
			visited[i] = false;
			series.pop_back();
		}
	}
}

void print() {
	for (int i = 0; i < M; i++) {
		cout << series[i] << ' ';
	}
	cout << "\n";
}