[백준 BOJ][C++]15649번 N과 M(1) 풀이: 브루트 포스 & DFS

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

15649번: N과 M (1)

 

 이 문제는 브루트 포스 문제로 명시되어 있지만 DFS를 사용하여 해결할 수 있습니다. 

 

 작은 수부터 차례대로 수를 트리 형태로 나타낼 수 있는데요.

 

 DFS 를 쓰고 싶게 생기지 않았나요! ㅎㅎ

 

 작은 수 부터 순차적으로 탐색하여 depth를 증가시켜 가며 탐색하면 됩니다. 

 

 이때 탐색 과정에서 visit을 true로 해주어 중복이 안되게 해야합니다. 다만 해당 노드의 자식 노드의 탐색이 끝나고 난 뒤 다시 visit을 false로 set 하여 다른 경로에서 다시 쓰일 수 있도록 해주는 것이 포인트입니다. 

 

 탐색한 노드들을 arr 배열에 저장한 뒤 depth가 m-1과 같아지면 arr 배열의 원소들을 출력하고 탐색을 종료합니다. 

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<cmath>

using namespace std;

int n, m;
bool visit[9] = { false, };
int arr[9];

void dfs(int depth) {

	if (depth == m - 1) {
		for (int i = 0; i < m; i++) {
			printf("%d ", arr[i]);
		}
		printf("\n");

		return;
	}

	for (int i = 1; i <= n; i++) {
		if (!visit[i]) {
			visit[i] = true;
			arr[depth + 1] = i;
			dfs(depth + 1);
			visit[i] = false;
		}
	}

}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		visit[i] = true;
		arr[0] = i;
		dfs(0);
		visit[i] = false;
	}

	return 0;
}