백준 15649번 N과 M (1) [C++]

알고리즘 공부 1주차 - 재귀함수

재귀함수에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천. 

알고리즘 공부 1주차(01): 재귀함수 개념

알고리즘 공부 1주차(01): 재귀함수 개념

백준 15649번 N과 M (1)

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

15649번: N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

예제 입력 1 

3 1

예제 출력 1

1 2 3

예제 입력 2 

4 2

 예제 출력 2

 

---

문제 설명

먼저 수열이 정확히 무엇인지 살펴보자면 

수열: 수가 배열되어 있는 것(줄 서있는 것)이다.

문제에서는 1부터 N까지의 자연수 중 M개를 줄 세우는 것이므로 4와 2를 골랐을때 1부터 4까지 중 중복없이 2개를 고른 수열이 예제 출력 2번과 같은 출력결과가 나오는 것이다.

여기서 키워드는 중복 없이이다. 1~n까지의 숫자가 중복되어선 안되며 꼭 m개의 숫자여야 하는 것이다. 

그럼 이제 수열 함수를 재귀함수를 통해 만들어보려면 필요한 것이 몇가지 있다. 

void go(int a) {
    if (a == m) {
        for (int i = 0; i < m; i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            ans[a] = i;
            go(a + 1);
            ans[a] = 0;
            visited[i] = false;
        }
    }
    return;
}

1. 함수가 반복된 개수로도 볼 수 있으며 기저조건을 만들기 위해 int a라는 매개변수 인자값을 추가한다. (a=0)

2. 1~n까지의 숫자이므로 반복문을 사용한다. 

3. 방문배열(visited배열)을 통해 방문했다면 해당 인덱스에 true를 넣는다. 

4. 정답배열(ans배열)에 방문배열에 넣었던 인덱스 값(사용된 i값)을 넣는다.

이때 넣을 인덱스는 함수가 실행될때마다 늘어나는 개수이므로 a인덱스에 대입한다.

5. a가 m까지 반복하는 것이므로 재귀함수 이름(a+1)을 통해 m이 될때까지 반복하도록 기저조건을 만든다. 

6. 만약 a가 m이 된다면(a랑 m이 같다면) ans의 값을 m개 출력하고, return한다. 

7. 다시 함수가 원래 자리로 돌아와 다음 코드를 실행하므로 2번 방문배열에 false를 넣고, 3번 정답 배열에 0을 넣는다. //초기화

8. 정리가 되었으면 다시 i가 n까지 반복하여 또 다른 배열을 만든다.  

 

글로 설명했을때 잘 이해가 안가면 직접 숫자 4, 2를 넣고 코드를 한줄씩 따라가보는 것이 좋다. 

1. a=0일때 

i=1에서 visited[1]==0(false) 이므로 visited[1] = true, ans[0] = i가 된다. 

go(0+1)을 실행한다

2. a=1일때

i=1에서 visited[1]==true이므로 넘어간다

i=2에서 visited[2]==false이므로 visited[2]=true; ans[1]=i가 된다. 

go(1+1)을 실행한다

3.a=2일때 

m=2이므로 a==m이다. 따라서 현재 ans인 1,2 값을 출력하고 return한다. 

4. go(1+1)로 돌아왔을때 (a=1일때)

현재 i=2에서 visited[2]=false, ans[1]=0이 된다. //기존값 초기화, 2가 사라짐

다시 반복문으로 돌아 i는 n까지 이므로 i=3이 된다.

i=3일때 visited[3]=false이므로 visited[3]=true,ans[1]=i가 된다. 

go(1+1)을 실행한다

5. a=2일때

m=2이므로 a==m이다. 따라서 현재 ans의 값 1,3 값을 출력하고 return한다.

4번으로 돌아간다.

위 과정을 반복하다 보면 한번씩 모든 수를 거쳐 중복되지 않는 경우의 수를 만드는 코드가 된다.     

---

제출한 코드(c++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int n, m, ans[9],visited[9];
void go(int a) {
    if (a == m) {
        for (int i = 0; i < m; i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            ans[a] = i;
            go(a + 1);
            ans[a] = 0;
            visited[i] = false;
        }
    }
    return;
}
int main(void) {
    cin >> n >> m;
    go(0);
    return 0;
}