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

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

15649번: N과 M (1)

순열 구하는 문제

# 1 <= M, N <= 8

import sys

readline = sys.stdin.readline


def recursive(n, r, selected_numbers):
    if len(selected_numbers) == r:
        print(" ".join(map(str, selected_numbers)))
        return

    for num in range(1, n + 1):
        if num in selected_numbers:
            continue

        new_selected_numbers = selected_numbers + [num]
        recursive(n, r, new_selected_numbers)


def permutation(n, r):
    selected_numbers = []
    recursive(n, r, selected_numbers)


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

permutation(n, m)

위 방법은 rest_numbers 배열을 넘기지 않는다.

# 1 <= M, N <= 8

import sys

readline = sys.stdin.readline


def recursive(r, selected_numbers, rest_numbers):
    if len(selected_numbers) == r:
        print(" ".join(map(str, selected_numbers)))
        return

    for num in rest_numbers:
        new_selected_numbers = selected_numbers + [num]
        new_rest_numbers = [k for k in rest_numbers if k != num]
        recursive(r, new_selected_numbers, new_rest_numbers)


def permutation(n, r):
    rest_numbers = [i for i in range(1, n + 1)]
    selected_numbers = []
    recursive(r, selected_numbers, rest_numbers)


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

permutation(n, m)

파이썬의 itertools를 사용하지 않고 직접 구현해봤다. 재귀함수 아직도 익숙하지가 않아..

원리 -  이미 선택한 숫자는 또 탐색하지 않고 건너뛰면서 다음 숫자를 재귀적으로 탐색한다. 사실상 완전 탐색 문제라고 봐도 될 듯..? 선택한 숫자의 개수가 조건에 맞으면 탐색을 멈춘다.

나뭇가지 그림을 그려보면 쉬운데, 예를들어 4P3을 해야하면

선택 1	선택 2	선택 3
1	2	3
		4
	3	2
		4
	4	2
		3
...	...	...

요런 식으로 그림을 그려서 경우의 수가 24가지인 것을 알 수 있다. 총 3번의 선택을 하고, 각각의 선택마다 가능한 경우를 또 탐색해나가야 한다.

반복문으로 구현해보려고 했는데, 트리가 n개만큼 생기는 거라서 좀 어려웠다.