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

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

15663번: N과 M (9)

 

 이 문제는 기존 N과 M 문제와 크게 다르지 않습니다. 

 

 다만 입력으로 주어지는 N개의 수에 중복되는 수가 있다는 것 인데요.

 

 변수 하나만 추가하면 해결할 수 있습니다. 

 

 입력으로 주어지는 수열을 sort() 함수를 통해 오름차순 정렬하면 작은 수 부터 차례대로 DFS를 수행하겠죠?

 

 이때 동일한 수열이 나오지 않게 하기 위해선 해당 노드에서 동일한 자식 노드를 두 번 이상 생성하면 안 됩니다. 

 

 예시로 N=4, M=4, 9 7 9 1을 들겠습니다.

 

 그럼 배열은 1 7 9 9 로 정렬되겠죠?

 

 부분적으로 봤을 때, 1로 시작하는 수열은 다음과 같이 트리 형태로 뻗어나갈 것입니다. 

 

 입력으로 들어온 9는 엄연히 2개 이니까 다음 레벨을 탐색할 때도 9를 두 번 생성해야 할까요?

 

 그렇게 되면 중복되는 수열이 생기게 됩니다. 

 

 그렇기 때문에 하나의 노드에서 다음 자식 노드로 뻗어나갈 때, 동일한 수를 가지는 노드 방향은 1번만 탐색해야 합니다.

 

 이것을 막기 위해 변수 check를 선언하여 이전 탐색한 자식 노드의 정보를 담고 다음 자식 노드가 이전 자식 노드와 다를 때만 dfs를 실행하도록 하였습니다. 

 

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

using namespace std;

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

void dfs(int depth) {

	if (depth == m - 1) {

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

	int check = 0;

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

int main(void) {

	int check = 0;

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

	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}

	sort(num, num + n);
	
	for (int i = 0; i < n; i++) {

		if (check == num[i])
			continue;

		memset(visit, false, sizeof(visit));
		visit[i] = true;
		check = num[i];
		arr[0] = num[i];
		dfs(0);
		visit[i] = false;
	}

	return 0;
}