[BOJ 15649] N과M(1) (C++)

www.acmicpc.net/problem/15649

15649번: N과 M (1)

N과M(1) 문제

구현 방법

 

N과M(1)은 백트래킹을 연습할 수 있는 N과 M시리즈 중 첫 번째 문제입니다.

 

1부터 N까지 자연수 중, 중복 없이 M개를 고른 수열을 출력해야합니다.

 

이를 위해 1부터 N까지 탐색하는데, 만약 현재 탐색하는 숫자가 이전에 사용됐으면 스킵하고, 사용하지 않았으면 answer배열에 추가시켜줍니다.

 

탐색을 하다가, 출력할 개수인 m번 진행되면, answer배열에 들어있는 m개의 원소를 모두 출력해주고 돌아갑니다.

 

예를 들어 n=4이고 m=3일 때 예를 들어 시뮬레이션을 해보겠습니다.

 

1) func(0)

func(0)에서 1~n까지 탐색

1은 사용된 적 없으니 arr의 k번째 원소를 1로 변경하고 isused[1] = 1로 해준 뒤 func(1) 호출

arr : [ 1 ]

isused: [ 1 ]

 

2) func(1)

func(1)에서 1~n까지 탐색

1은 사용된 적 있으니 스킵

2는 사용된 적 없으니 arr의 k번째 원소를 2로 변경하고 isused[2] = 1로 해준 뒤 func(2) 호출

arr : [ 1 , 2 ]

isused: [ 1 , 1 ]

 

3) func(2)

func(1)에서 1~n까지 탐색

1은 사용된 적 있으니 스킵

2는 사용된 적있으니 스킵

3은 사용된 적 없으니 isused[3] = 1로 해준 뒤 func(3) 호출

arr : [ 1 , 2 , 3 ]

isused: [ 1 , 1 , 1 ]

 

4) func(3)

func(3)에서 m이 3이니 k==m 만족해 출력 부분으로 들어가 arr의 모든 원소 출력 후 종료

arr : [ 1 , 2 , 3 ]

isused: [ 1 , 1 , 1 ]

 

5) func(2)

func(3) 호출한 뒤, func(3)이 위처럼 종료되었으니

isused[3] = 0으로 되돌려 준 뒤 계속 탐색

4는 사용된 적 없으니 arr의 k번째 원소를 4로 변경하고 isused[4] = 1로 해준 뒤 func(3) 호출

arr : [ 1 , 2 , 4 ]

isused: [ 1 , 1 , 0 , 1 ]

 

6) func(3)

func(3)에서 m이 3이니 k==m 만족해 출력 부분으로 들어가 arr의 모든 원소 출력 후 종료

arr : [ 1 , 2 , 4 ]

isused: [ 1 , 1 , 0 , 1 ]

 

7) func(2)

func(3) 호출한 뒤, func(3)이 위처럼 종료되었으니

isused[4] = 0으로 되돌려 준 뒤 계속 탐색

func(2)에서 1~n, 즉 1~4까지 탐색 모두 완료했으니 종료

arr : [ 1 , 2 , 4 ]

isused: [ 1 , 1 , 0 , 0 ]

 

8) func(1)

func(2) 호출한 뒤, func(2)가 위처럼 종료되었으니

isused[2] = 0으로 되돌려 준 뒤 계속 탐색

3은 사용된 적 없으니 arr의 k번째 원소를 3으로 변경하고 isused[3] = 1로 해준 뒤 func(3) 호출

arr : [ 1 , 3 , 0 ]

isused: [ 1 , 0 , 1 , 0 ]

 

... 이렇게 계속됩니다.

 

위 내용을 아래와 같이 구현했습니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
//출력할 원소들을 저장할 배열
int answer[10];

//1~n숫자중 사용 됐는지 안됐는지 저장할 배열
int isused[10];

//func(k)함수는, 수열의 k번째 수를 정하는 함수
void func(int k) {

	//k가 출력하고자 하는 수열의 개수와 같으면 수열 길이만큼 출력
    if(k == m) {
        for(int i=0;i<m;i++) {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }
	
    //1~n까지 탐색하면서, 해당 숫자 사용 안했으면 출력할 배열에 추가해주고,
    //사용했다고 표시한 후 다음 원소 결정.
    //다음 원소 결정이 끝나고 되돌아오면, 사용 표시 제거
    for(int i=1;i<=n;i++) {
        if(!isused[i]) {
            answer[k] = i;
            isused[i] = 1;
            func(k+1);
            isused[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    func(0);
}