[백준 15649번 C++] N과 M(1)

DFS를 사용하여 푸는 대표적인 문제중 하나.

순열 문제도 DFS를 사용하여 풀 수 있다는 것에 유의! 

 

문제의 조건에 따라 케이스를 손으로 직접 쓰고, 눈에 보이는 규칙을 정리해서 그대로 코드로 구현하는 과정이 재밌다 :) 

Check Point

 

1. DFS에서 재귀를 사용할 때의 기본 조건과, 배열 내 데이터를 삽입하고 삭제할때를 유의하여 코드를 구현한다.

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

15649번: N과 M (1)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> arr;
bool visited[8];

void DFS(int depth) {

	if (depth == M) {
		for (int i = 0; i <M; i++) {
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (visited[i]==false) {
			visited[i] = true;
			arr.push_back(i);
			DFS(depth + 1);
			visited[i] = false;
			arr.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	cin >> N >> M;

	DFS(0);
}