[BOJ] 15649번: N과 M(1)

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

15649번: N과 M (1)

 

Python3

백트랙킹 알고리즘으로 해결하는 방식과 파이썬 내장함수를 사용하여 해결하는 방식 2가지로 풀어보았다.

 

Code 1

from itertools import permutations

if __name__ == '__main__':
    N, M = map(int, input().split())
    numbers = [i for i in range(1, N+1)]
    for item in permutations(numbers, M):
        print(*item, sep=" ")

itertools 모듈의 permutations 내장함수를 사용하여 쉽게 해결할 수 있었다 permutations 함수 사용을 위해 1부터 주어진 N까지의 범위 내로 배열을 만들어주었다. M개를 선택하는 것으로 permutations를 실행하였고 반복문을 통해 결과를 받을 수 있었다. item은 튜플형이기 때문에 튜플을 풀어주고 띄어쓰기로 분류해주었다.

 

Code 2 

def dfs(time, numbers=[]):
    if time == 0:
        print(*numbers, sep=" ")
        return
    for i in range(1, N+1):
        if i not in numbers:
            new_numbers = numbers.copy()
            new_numbers.append(i)
            dfs(time-1, new_numbers)


if __name__ == '__main__':
    N, M = map(int, input().split())
    dfs(M)

백트랙킹을 통한 문제풀이다. dfs를 통해 코드를 작성하였고 이때 두가지의 조건문이 필요하다. 첫번째 M개의 숫자를 골랐는지, 두 번째 이미 고른 수가 아닌지 이 두가지에 대해 확인하는 과정이 필요하다. M개의 숫자를 골랐다면 고른 수들을 출력해주었다. 아니라면 범위내의 숫자를 오름차순으로 하나씩 보면서 선택되지 않은 수일경우 선택하고 앞으로 골라야할 수의 개수를 줄여 dfs를 실행시켰다.

 

N=4, M=3 일때 트리 형태