백준(BaekJoon) 15649 : N 과 M (1) c++

▶문제 : 15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

 

▶코드 작성(아래에 개선 코드)

#include <iostream>

int n, m;
int arr[8];//한 줄로 출력할 수의 배열

void print(int i) {//i : arr배열의 자리
    bool b;
    for (int j = 1; j <= n; j++) {
        b = true;
        for (int l = 0; l < i; l++) {//arr배열에 숫자 j가 있는지 확인
            if (arr[l] == j) {
                b = false;
                break;
            }
        }

        if (b) arr[i] = j;//arr배열에 없으면 j 대입
        
        if (i + 1 == m && b) {//출력할 수의 길이가 m과 같으면 출력
            for (int l = 0; l < m; l++) {
                std::cout << arr[l] << ' ';
            }
            std::cout << std::endl;
        }
        else if (b) print(i + 1);//아직 arr배열의 길이가 m보다 작으면 재귀함수
    }
}

int main() {
    std::cin >> n >> m;

    print(0);//맨 앞자리 0부터 시작
}

반복문을 사용해서 arr배열에 이미 들어가 있는 수인지 찾는 방법이 비효율적이었다.

 

▶개선 코드

#include <iostream>

int n, m;
bool num[8] = { false, };//사용했는지 여부
int arr[8];//한 줄로 출력할 수의 배열

void print(int i) {//i : arr배열의 자리
    if (i == m) {//arr배열의 길이가 m이라면 출력
        for (int j = 0; j < m; j++) {
            std::cout << arr[j] << ' ';
        }
        std::cout << std::endl;
        return;
    }

    for (int j = 0; j < n; j++) {
        if (num[j] == true) continue;//이미 배열에 들어간 수라면 패스
        num[j] = true;//j+1 숫자를 배열에 넣었다는 표시
        arr[i] = j + 1;//배열 대입
        print(i + 1);//다음 자리에 넣을 수를 찾으러 재귀함수 사용
        num[j] = false;//배열에서 해제
    }
}

int main() {
    std::cin >> n >> m;

    print(0);//맨 앞자리 0부터 시작
}

 

▶해석

백트래킹 알고리즘으로 분류되어있는 문제이다. 모든 경우의 수를 찾되 조건을 넣어주어 불필요한 경우를 제외시켰다.

 

출력할 배열인 arr와 arr배열에 대입했는지 판별할 수 있도록 num배열을 선언하였다.

재귀 함수를 이용하여 출력할 맨 앞자리 0부터 시작하였다.

 

print함수에서 i는 arr배열의 길이라고 봐도 무방하므로 i==m 일 때 출력하는 조건에 일치하여 arr배열을 출력해준다.

 

arr배열에 수를 대입하는 for문에서는 0부터 n-1까지 반복하여 num배열에서 true 또는 false인지 확인하고 true면 이미 arr배열에 들어가 있다는 뜻이므로 다음 수로 넘어간다.

false라면 arr배열에 수를 입력할 것이므로 true로 바꿔준 후 arr배열에 대입한다.

배열 자리 i에 대입했으므로 다음 자릿수를 찾으러 print 함수를 호출한다.

재귀 함수가 끝나면 바로 false로 바꿔주어 arr배열에서 제외시켰다는 것을 표시한다.