[백준/백트래킹] 15649번: N과 M(1) (실버3, python)

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

15649번: N과 M (1)

아이디어

순열을 구하는 문제였다. dfs로 모든 경우의 수를 탐색하면서, 백트래킹으로 겹치는 숫자를 만나지 않게 제외해주면 된다!

 

전체코드

N, M = map(int, input().split())

visited = [0] * (N + 1)

def bt(nums, visited):
    if len(nums) == M:
        for num in nums: 
            print(num, end=" ")
        print()
        return
    
    for idx in range(1, N + 1):
        if visited[idx] == 0:
            visited[idx] = 1
            bt(nums+[idx], visited)
            visited[idx] = 0
            
bt([], visited)

제너레이터를 이용해서 구현

처음에는 제너레이터로 편하게 구현했는데 N과 M 시리즈가 여러개라서.. 나중에 후회할까봐 정석 코드로 다시 짰다.

N, M = map(int, input().split())

def gen(prefix, nums, M):
    if len(prefix) == M:
        yield prefix
        return
    for idx, num in enumerate(nums):
        if num not in prefix:
            yield from gen(prefix+[num], nums[:idx]+nums[idx+1:], M)

answer = list(gen([], [x for x in range(1, N+1)], M))

for ans in answer:
    for a in ans:
        print(a, end=" ")
    print()

아래 제출한게 제너레이터로 작성한 코드이다. 시간이 70ms정도 짧아졌다!!~