BOJ DFS(逆追跡):NとM(1)(15649)


質問する
自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.
1からNまで自然数の中でM個の数列を繰り返し選択しない
入力
第1行は自然数NとMを与える.(1 ≤ M ≤ N ≤ 8)
しゅつりょく
各行に問題条件を満たす数列を出力します.重複する数列は複数回出力できません.各数列はスペースで区切らなければなりません.
数列は予め増加した順序で出力しなければならない.
I/O例

試す
  • の正解がありますが、ランタイムエラー
  • が発生しました.
    # itertools의 combination은 순서에 따라 중복X
    # itertools의 permutations은 순서 상관없이 중복O
    
    from itertools import permutations as p
    
    n, m = map(int, input().split(' '))
    n, m = 4, 2
    lst = [x for x in range(1, n+1)]
    for i in  p(lst,m):
        print(i[0], i[1])
    解答コード1:itertoolsを利用
    from itertools import permutations as p
    
    n, m = map(int, input().split(' '))
    n, m = 4, 2
    
    lst = [x for x in range(1, n+1)]
    lst_p = list(p(lst, m))
    
    for i in range(len(lst_p)):
        for j in range(m):
            print(lst_p[i][j], end = " ")
        print()
    正しいコード2:遡及を利用する
    n, m = 3, 2
    def dfs():
        if len(lst) == m:
            print(' '.join(map(str,lst)))
            return
        for i in range(1, n+1):
            if i not in lst:
                lst.append(i)
                dfs()
                lst.pop()
    dfs()
    遡及はDFSベースの応用アルゴリズムである.
    与えられた問題の答えを解くために,現在の状態で可能な限りすべての候補群に従って探索するアルゴリズム.
    BOJのNとM(1-9)シリーズはバックグラウンドの練習にぴったりです.
  • バックグラウンドトラッキングに基づいて,再帰関数を再理解するためにコード実行順序を整理した.
  • FIRST MAIN LOOP #############################################################
    
    dfs1 : i == 1 : [1]     # append
    
    dfs2 : i == 1 : ----------------
    
    dfs2 : i == 2 : [1,2]   # append
    dfs3 : return [1,2]
    dfs2 : i == 2 : [1]     # pop
    
    dfs2 : i == 3 : [1,3]   # append
    dfs4 : return [1,3]
    dfs2 : i == 3 : [1]     # pop
    
    dfs1 : i == 1 : []      # pop
    
    SECOND MAIN LOOP #############################################################
    
    dfs1 : i == 2 : [2]     # append
    
    dfs5 : i == 1 : [2,1]   # append
    dfs6 : return [2,1]
    dfs5 : i == 1 : [2]     # pop
    
    dfs5 : i == 2 : ----------------
    
    dfs5 : i == 3 : [2,3]   # append
    dfs7 : return [2,3]
    dfs5 : i == 3 : [2]     # pop
    
    dfs1 : i == 2 : []      # pop
    
    THIRD MAIN LOOP #############################################################
    
    dfs1 : i == 3 : [3]     # append
    
    dfs8 : i == 1 : [3,1]   # append
    dfs9 : return [3,1]
    dfs8 : i == 1 : [3]     # pop
    
    dfs8 : i == 2 : [3,2]   # append
    dfs10: return [3,2]
    dfs8 : i == 2 : [3]     # pop
    
    dfs8 : i == 3 : -----------------
    
    dfs1 : i == 3 : []      # pop
    
    #############################################################