15649 N과 M_1(백트랙킹)

백트랙킹

-알고리즘은 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모로 되돌아간 후 다른 자식 노드를 검색하는 알고리즘이다.

출처

15649번: N과 M (1)

 

내 코드

n, m = map(int, input().split())
visited = [-1] * n
out = []
def solve(depth, m):
    if depth == m:
        print(' '.join(map(str, out)))
        return

    for i in range(n):
        if i+1 not in visited:
            visited[i] = i+1
            out.append(i+1)
            solve(depth+1, m)
            visited[i] = -1
            out.pop()

solve(0, m)

• i가 0번째부터 시작하므로 visited의 값을 -1로 리스트를 만들어준다.
• 방문하지 않은 정수에 대해서 dfs 작업을 해준다.