BOJ 15649 - N과 M

N과 M - 🥈 Silver 3

• 문제 링크
  https://www.acmicpc.net/problem/15649

처음 문제를 접하였을때는 특정 개수의 숫자를 넣어 next-permutation을 이용하는 문제라고 생각했지만, 지정된 개수만큼 1부터 N 사이의 서로 다른 숫자를 고르는 것이 문제였다.

이 문제는 백트래킹을 이용하면 쉽게 풀이할 수 있다.

백트래킹 - Back Tracking

• 가능한 모든 경우의 수 중에서 조건에 부합한 경우를 탐색

이는 DFS를 활용하여 풀이할 수 있다. 1부터 N까지의 숫자중에서 M개를 선택하며, 서로 다른 숫자여야하므로 이미 사용한 숫자를 다시 사용하지 않도록 이를 표시하며 DFS를 수행한다. 사용 여부는 각 숫자에 대하여 vector를 이용하여 index로 접근하여 판단이 가능하도록 true, false로 표시하였다. 이를 정리하면 아래와 같다.

풀이 방법

• 선택한 숫자가 M개가 아닐 경우
  - 1부터 N까지 탐색
  - 탐색 중에 해당 숫자를 사용하지 않았다면, 결과를 저장할 vector에 넣고, used를 true로 표시
  - 이후 선택한 숫자의 개수를 인자로 넘겨주며 다시 DFS 실행
  - 재귀 수행 이후, vector에 삽입한 값을 제거하고 used를 false로 표시
• 선택한 숫자가 M개일 경우
  - 결과가 저장된 'vector'를 출력하고 return

이에 대한 코드는 아래와 같다.

풀이 코드

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

int N, M;
// 특정 숫자를 선택했는지를 저장할 vector
vector<bool> used;
// 결과를 저장할 vector
vector<int> result;

// 백트래킹하여 모든 경우의 수를 출력할 DFS 함수
void DFS(int count) {
	// count가 M과 같은 경우, result 안에 N개의 서로 다른 숫자가 존재
	if (count == M) {
    	// 결과 출력 후 return
		for (auto iter : result) {
			cout << iter << " ";
		}
		cout << "\n";
		return;
	}
    // M개보다 적게 있는 경우
	else {
    	// 숫자를 탐색
		for (int i = 0; i < N; i++) {
        	// 사용하지 않은 숫자라면
			if (!used[i]) {
            	// result에 삽입 이후 사용여부를 표시
				result.push_back(i + 1);
				used[i] = true;
                // count를 1 증가시켜 재귀 수행
				DFS(count + 1);
                // 수행 이후 원래대로 복원
				result.pop_back();
				used[i] = false;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
    // 입력값 입력받음
	cin >> N >> M;
	
    // used vector 모두 false로 초기화 (숫자 개수만큼 초기화)
	for (int i = 1; i <= N; i++) {
		used.push_back(false);
	}
	
    // DFS 수행
	DFS(0);

	return 0;
}

결과