[BAEKJOON] 15663 N과 M(9) (C++)

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

15663번: N과 M (9)

Solved.ac 4단계에 N과 M 시리즈가 있길래 이번에 풀어보았다. 

그 중 하나가 시리즈 9번째인 15663번 문제이다.

 

Backtracking 문제라고 한다.

Backtracking은 DFS를 진행하는 과정에서 답이 될 수 없는 경우 해당 경로 탐색을 중지하고 다시 돌아가는 알고리즘이다. 즉 DFS를 좀 더 효율적으로 하는 방법이라고 볼 수 있다.

 

문제

N개의 수가 주어졌을 때 해당 수들을 이용해 길이가 M인 수열을 만드는 문제이다.

이때 오름차순, 중복수열은 제외 해야하는 조건이 있다.

또 N과M(9)의 경우는 N개의 수중 중복되는 수가 존재한다는 특징이 있다.

 

 

N과 M 시리즈의 풀이는 기본적으로 비슷하다.

DFS를 활용하여 출력할 수들을 A배열에 저장한다.

매개변수로는 수열의 몇번째 수를 결정할 것인지를 받아서 해당 번째의 수를 결정한다.

이때 결정된 수는 visited 배열에 표시하고 재귀호출을 한다. 호출이 끝난 시점에서는 visited배열의 방문여부를 다시 해제해준다.

 

여기까지가 기본적인 N과 M문제의 베이스 풀이다.

(9)번 의 경우는 중복된 수가 존재한다.  

처음에는 중복되는 수를 어떻게 확인해야할지 고민하다가 잘 결론이 안 나서 조금 무식하게 해결했다.

 unordered_map을 이용해서 마지막 출력 전에 해당 수열이 출력된 적이 있는지 확인하는 것. 답은 나왔지만 상당히 비효율적이었다.

더 좋은 풀이로는 바로 이전에 cnt번째에 결정된 수가 cnt번째에 넣으려는 수와 동일하면 이미 이전에 나왔던 케이스와 동일한 것이므로 제외하는 방법이 있다. (수를 정렬시킨 후 탐색하기 때문에 성립한다.) 이렇게 하는 경우 불필요한 탐색을 중지하기 때문에 백트레킹을 이용했다고 볼 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"

using namespace std;

int N, M;
vector<int> num;
int A[10];
int visited[10];
void dfs(int cnt) {
	if (cnt == M) {
		for (int i = 0; i < M; i++) cout << A[i]<<" ";
		cout << endl;
		return;
	}
	int tmp = -1;
	for (int i = 0; i < num.size(); i++) {
		if (visited[i] == 1 || tmp == num[i]) continue;
		tmp = num[i];
		visited[i]=1;
		A[cnt] = num[i]; dfs(cnt + 1); 
		visited[i]=0;
	}
}

void Solve() {
	int k;
	cin >> N>>M;
	for (int i = 0; i < N; i++) {
		cin >> k;
		num.push_back(k);
	}
	sort(num.begin(), num.end());
	dfs(0);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Solve();


	return 0;
}

배운 점

 

또 수열에서 특정 값이 이미 나온적이 확인하는 배열 visited의 size를 10000으로 설정하여 수 자체를 인덱스로 하였는데, 그냥 i번째 수를 수열에 포함한 적이 있는지 확인하면 된다. -> visited 배열의 size는 8이면 충분하다.

무작정 수를 인덱스로 하여 방문여부를 확인할 게 아니라 인덱스 자체를 이용해 방문여부를 확인할 수 있는지 고려해서 메모리 사용을 효율적으로 할 수 있다는 점을 알았다.