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

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/f36567ec0c9f44b4b460b5b29683c27b
#include <bits/stdc++.h>
using namespace std;

int n,m;
int arr[10];
bool isused[10];

void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }

  for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 수를 i로 정함
      isused[i] = 1; // i를 사용되었다고 표시
      func(k+1); // 다음 수를 정하러 한 단계 더 들어감
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

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

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

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

 

참고 해설 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/solutions/15649.cpp

basic-algo-lecture/0x0C/solutions/15649.cpp at master · encrypted-def/basic-algo-lecture

 

자바와 비교

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

• #include <bits/stdc++.h>: C++의 모든 표준 라이브러리를 포함하는 헤더 파일입니다. 자바의 import java.util.*;와 비슷합니다.
• using namespace std;: 표준 네임스페이스를 사용하겠다는 선언입니다. 자바에서는 패키지를 지정하지 않고 바로 사용할 수 있게 하는 것과 유사합니다. 이를 통해 코드에서 std::를 생략하고 표준 라이브러리의 기능을 바로 사용할 수 있게 됩니다.

int n, m;
int arr[10];
bool isused[10];

• int n, m;: 두 개의 정수 변수 n과 m을 선언합니다.
• int arr[10];: 최대 10개의 정수를 저장할 배열 arr를 선언합니다.
• bool isused[10];: 최대 10개의 불리언 값을 저장할 배열 isused를 선언합니다. 각 숫자가 사용되었는지 여부를 저장합니다.

void func(int k) {

• void func(int k): 반환값이 없는 함수 func를 선언합니다. 매개변수 k는 현재까지 선택한 숫자의 개수를 나타냅니다.

  if (k == m) {
    for (int i = 0; i < m; i++)
      cout << arr[i] << ' ';
    cout << '\n';
    return;
  }

• if (k == m): k가 m과 같으면, 즉 m개의 숫자를 모두 선택했으면 아래 코드를 실행합니다.
• for (int i = 0; i < m; i++): arr 배열에 저장된 m개의 숫자를 출력합니다.
• cout << arr[i] << ' ';: arr 배열의 i번째 요소를 출력합니다. 자바의 System.out.print(arr[i] + " ");와 유사합니다.
• cout << '\n';: 줄 바꿈을 출력합니다. 자바의 System.out.println();과 유사합니다.
• return;: 함수를 종료합니다.
  1. func(k + 1);이 호출되고, 재귀적으로 func함수가 실행됩니다.
  2. 재귀 호출이 끝나면, isused[i] = 0;이 실행됩니다.
  3. for 루프의 다음 반복으로 넘어가서 다음 숫자를 확인합니다.

  for (int i = 1; i <= n; i++) {
    if (!isused[i]) {
      arr[k] = i;
      isused[i] = 1;
      func(k + 1);
      isused[i] = 0;
    }
  }
}

• for (int i = 1; i <= n; i++): 1부터 n까지의 숫자를 반복합니다.
• if (!isused[i]): i가 아직 사용되지 않았으면 아래 코드를 실행합니다.
• arr[k] = i;: k번째 위치에 i를 저장합니다.
• isused[i] = 1;: i를 사용되었다고 표시합니다.
• func(k + 1);: 다음 숫자를 선택하기 위해 재귀 호출합니다.
• isused[i] = 0;: k번째 위치에 i를 저장한 모든 경우를 확인했으므로 i를 사용되지 않았다고 표시합니다.

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

• int main(void): 프로그램의 시작점인 main 함수입니다.
• ios::sync_with_stdio(0);: C++의 입출력 속도를 향상시키기 위한 설정입니다.
• cin.tie(0);: 입출력의 묶음을 풀어줍니다.
• cin >> n >> m;: 사용자로부터 n과 m을 입력받습니다. 자바의 Scanner를 사용한 입력과 유사합니다.
• func(0);: func 함수를 호출하여 백트래킹을 시작합니다.

 

예제 ) n = 4이고, m = 3일 때 흐름 따라가기

1. func(0)에서 i = 1일 때:
   • arr[0] = 1, isused[1] = true.
   • func(1) 호출.
2. func(1)에서 i = 2일 때:
   • arr[1] = 2, isused[2] = true.
   • func(2) 호출.
3. func(2)에서 i = 3일 때:
   • arr[2] = 3, isused[3] = true.
   • func(3) 호출.
4. func(3)에서 k == m이므로 123 출력 후 return.
5. func(2)로 돌아와서 isused[3] = false.
6. func(2)에서 다음 반복으로 i = 4일 때:
   • arr[2] = 4, isused[4] = true.
   • func(3) 호출.
7. func(3) 호출:
   • k == 3이므로 if (k == m) 조건은 true.
   • arr 배열 출력: 1 2 4.
   • return 후 isused[4] = false.
8. func(2)로 돌아와서 다음 반복:
   • i = 4까지 반복이 끝났으므로 func(1)으로 돌아감.
   • isused[2] = false.
9. func(1)으로 돌아와서 다음 반복:
   • i = 3일 때: arr[1] = 3, isused[3] = true, func(2) 호출.
10. func(2) 호출:
    • k == 2이므로 if (k == m) 조건은 false.
    • for 루프 시작, i = 1부터 n = 4까지 반복.
11. i = 1일 때:
    • isused[1]이 true이므로, 다음 반복으로 넘어감.
12. i = 2일 때:
    • isused[2]이 false이므로, arr[2] = 2, isused[2] = true.
    • func(3) 호출.
13. func(3) 호출:
    • k == 3이므로 if (k == m) 조건은 true.
    • arr 배열 출력: 1 3 2.
    • return 후 isused[2] = false.