[c++][python][백준 15649] N과 M (1)

백준 15649번: N과 M (1) [Silver 3]
https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

문제 풀이

• 이 문제는 DFS - 백트랙킹 문제입니다.
• 중복된 숫자 방지를 위한 check array와 순열의 숫자를 담은 array를 선언하여 순열 array에 M개의 숫자가 담기게 되면 해당 array를 출력하고 return 합니다.

코드 (c++)

#include <cstdio>

using namespace std;

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

void dfs(int idx) {
    if(idx == m) {
        for(int i=0; i<m; ++i) printf("%d ", arr[i]);
        putchar('\n');
        return;
    }
    
    for(int i=1; i<=n; ++i) {
        if(!check[i]) {
            check[i] = true;
            arr[idx] = i;
            dfs(idx+1);
            check[i] = false;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    dfs(0);
    return 0;
}

코드 (python)

n, m = map(int, input().split())

check = [False] * (n+1)
arr = [0] * m

def dfs(idx):
    if idx == m:
        print(' '.join(map(str, arr)))
        return
    
    for i in range(1, n+1):
        if not check[i]:
            check[i] = True
            arr[idx] = i
            dfs(idx+1)
            check[i] = False
            
dfs(0)

실행 결과