[백준/C언어] 15649번 - N과 M (1)

백준 웹사이트 "15649번 - N과 M (1)" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

15649번: N과 M (1)

---

소스 코드

#include <stdio.h>

void search(int * arr, int count, int N, int M);

int main(void){
    int N, M;
    scanf("%d %d", &N, &M);

    int arr[M];
    search(arr, 0, N, M);
}

void search(int * arr, int count, int N, int M){
    if(count==M){
        //print arr
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
    else{
        for(int i=1; i<=N; i++){
            int exists=0;
            for(int j=0; j<count; j++){
                if(arr[j]==i)
                    exists=1;
            }
            if(!exists){
                arr[count] = i;
                search(arr, count+1, N, M);
            }
        }
    }
}

---

문제 풀이

  백트래킹 (Backtracking)은 해결방안을 찾다가 어느 시점에서든 문제의 조건과 어긋나 막히게 되면 전 단계로 돌아가 새로운 방안을 찾는 기법입니다. 백트래킹을 이용할 때는 주로 재귀를 통해 점진적으로 해결방안을 찾아냅니다.

  이번 문제는 'search' 재귀함수를 정의하여 간단하게 풀 수 있습니다.

함수: search(int * arr, int count, int N, int M)

파라미터
- arr : 출력할 수열 (재귀를 통해 값들을 채움)
- count : 재귀 반복 횟수, 또는 배열 arr에 값을 채운 횟수
- N : 채우는 자연수의 범위 (1부터 N까지 자연수 중에서 고름)
- M : 출력할 수열의 길이

Base Case (기본 케이스)
- 조건문: count == M
- 실행문: 배열 arr 출력

Recursive Case (재귀 케이스)
- 조건문: count != M (count가 M보다 작을 경우)
- 실행문: 배열 arr을 확인하여 아직 배열 내에 존재하지 않는 자연수를 선택하여 arr에 추가, 재귀
- 재귀: search(arr, count+1, N, M)

 

  변수 'count'는 배열 arr에 값을 채운 횟수이므로 이 값이 arr의 크기인 M과 같아지면 배열 arr을 모두 채웠다는 뜻이 됩니다. 따라서 조건문 'count == M'이 만족되면 해당 배열이 출력되도록 하고, 만족되지 않으면 배열 arr을 확인하여 배열 내에 아직 존재하지 않는 수를 추가합니다. 이렇게 숫자 하나가 늘어난 arr을 파라미터로 search를 호출하면, 재귀가 일어납니다.

  이 문제의 경우, arr에 추가할 수 있는 숫자가 항상 존재하므로 사실 '백트래킹'이라고 불릴만한 과정이 일어나지는 않습니다. 백트래킹은 매우 비슷한 문제인 "15650번 - N과 M (2)"에 나타납니다. 어떠한 차이가 있는지 궁금하면 참고해주세요!

  아래는 백준 웹사이트 "15650번 - N과 M (2)" 문제풀이 링크입니다.

[백준/C언어] 15650번 - N과 M (2)