BOJ DFS(逆追跡):NとM(1)(15649)
質問する
自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.
1からNまで自然数の中でM個の数列を繰り返し選択しない
入力
第1行は自然数NとMを与える.(1 ≤ M ≤ N ≤ 8)
しゅつりょく
各行に問題条件を満たす数列を出力します.重複する数列は複数回出力できません.各数列はスペースで区切らなければなりません.
数列は予め増加した順序で出力しなければならない.
I/O例
試すの正解がありますが、ランタイムエラー が発生しました.
与えられた問題の答えを解くために,現在の状態で可能な限りすべての候補群に従って探索するアルゴリズム.
BOJのNとM(1-9)シリーズはバックグラウンドの練習にぴったりです.バックグラウンドトラッキングに基づいて,再帰関数を再理解するためにコード実行順序を整理した.
自然数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
#############################################################
Reference
この問題について(BOJ DFS(逆追跡):NとM(1)(15649)), 我々は、より多くの情報をここで見つけました https://velog.io/@yozzum/백트래킹-BOJ-N과-M1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol