c++ 백준_15663_"N과 M (9)"

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

15663번: N과 M (9)

 

어이고,,

나한테 좀 어려웠다..

​

몇번을 정렬이 문제인가

수열 뽑는게 문제인가

수정 계속하며 제출해도 틀렸다.

​

그래서 힌트를 보니 백트래킹이라고 해서

트리 형태로 그려보았다.

​

일단 입력 받은 배열을 정렬하고 진행했다.

​

예제 2로 예를 들면

정렬 후 배열은

1 7 9 9

​

(트리 형태라고 가정)

여기서 시작하면

(root)

1

7 9 9

(leaf)

​

형태이다

​

1 - 7 진행 후,

​

1의 가운데 자식인

1 - 9 를 갔다가

다음 맨 오른쪽 자식을 방문한 1- 9 는 같은

앞서 방문했던 같은 1 - 9 니까

제외시켜야된다.

​

그래서 부모 노드에서 자식 노드로 방문했던 마지막 지점(값)을 저장해서

부모가 그 다음 자식 노드를 확인할 때

마지막 저장 값과 같다면

더 이상 방문을 진행하지 않았다.(continue)

 

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

int N, M;

bool visit[8];
int number[8];


vector<int> temp;
void permu(int depth, int idx) {

	if (depth == M) {

		for (int i = 0; i < M; i++) {
			cout << temp[i] << " ";
		}
		cout << "\n";
		return;
	}
	int last = -1;
	for (int i = 0; i < N; i++) {
		if (last != -1) {
			if (last == number[i])
				continue;
		}
		if (!visit[i]) {
			temp.push_back(number[i]);
			visit[i] = true;
			permu(depth + 1, i);
			visit[i] = false;
			temp.pop_back();
			last = number[i];
		}
	}
}

int main(void) {

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> number[i];
	}

	sort(number, number + N);

	permu(0, 0);

}